プッシュダウン・オートマトンの能力
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/10/17 08:19 UTC 版)
「計算可能性理論」の記事における「プッシュダウン・オートマトンの能力」の解説
プッシュダウン・オートマトンが受容する言語のクラスを文脈自由言語と呼び、文脈自由文法によって記述される。正規言語でないとされた 'a' と 'b' を同数含む文字列からなる言語はプッシュダウン・オートマトンで判定可能である。また一般に、プッシュダウン・オートマトンを有限状態機械のように動作させることもできるので、正規言語も判定可能である。従ってこの計算モデルは有限状態機械よりも強力である。 しかし、プッシュダウン・オートマトンでも判定できない言語がある。その詳細は（正規言語のときとあまり変わらないので）ここでは述べない。文脈自由言語の反復補題も存在する。例えば、素数の集合からなる言語がその例である。
※この「プッシュダウン・オートマトンの能力」の解説は、「計算可能性理論」の解説の一部です。
「プッシュダウン・オートマトンの能力」を含む「計算可能性理論」の記事については、「計算可能性理論」の概要を参照ください。
ウィキペディア小見出し辞書の「プッシュダウン・オートマトンの能力」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- プッシュダウン・オートマトンの能力のページへのリンク
