「形式言語の階層」の版間の差分
削除された内容 追加された内容
新規 |
編集の要約なし |
||
| 30行目: | 30行目: | ||
|- |
|- |
||
| n/a |
| n/a |
||
| |
| [[木接合文法]] |
||
| [[弱文脈依存言語]] |
| （[[弱文脈依存言語]]） |
||
| [[w:Embedded pushdown automaton|Embedded プッシュダウン・オートマトン]] |
| [[w:Embedded pushdown automaton|Embedded プッシュダウン・オートマトン]] |
||
|- |
|- |
||
2008年5月3日 (土) 23:07時点における版
形式言語の包含階層はチョムスキー階層が知られているが、チョムスキーが1956年にチョムスキー階層を発表して以来、その４つのタイプ以外にも同じ階層上に存在する新たな形式言語のタイプが見つかっている。
| チョムスキー 階層 |
文法 | 言語 | オートマトン |
|---|---|---|---|
| タイプ-０ | 制限なし文法 | 帰納的可算言語 | チューリングマシン |
| n/a | 帰納言語 | Decider | |
| タイプ-１ | 文脈依存文法 | 文脈依存言語 | 線形拘束オートマトン |
| n/a | Indexed 文法 | Indexed 言語 | Nested-stack オートマトン |
| n/a | 木接合文法 | （弱文脈依存言語） | Embedded プッシュダウン・オートマトン |
| タイプ-２ | 文脈自由文法 | 文脈自由言語 | プッシュダウン・オートマトン |
| n/a | Deterministic 文脈自由文法 | Deterministic 文脈自由言語 | Deterministic プッシュダウン・オートマトン |
| タイプ-３ | 正規文法 | 正規言語 | 有限オートマトン |
| n/a | Star-free 言語 | Counter-Free Automata | |
| n/a | Locally threshold-testable language | ||
| n/a | Locally testable language | ||
| n/a | Strictly local language | Scanners |
Reference
 | この項目は、言語学に関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（ウィキポータル 言語学）。 |