「形式言語の階層」の版間の差分
削除された内容 追加された内容
+wikifyタグ. 統合や英語版のようにテンプレート空間に移すなどを検討する必要があるかも。 |
レイアウト |
||
1行目:
▲[[形式言語]]の[[ヒエラルキー|包含階層]]は[[チョムスキー階層]]が知られているが、[[チョムスキー]]が[[1956年]]にチョムスキー階層を発表して以来、その4つのタイプ以外にも同じ階層上に存在する新たな形式言語のタイプが見つかっている。
== 解説 ==
=== タイプ-0 ===
=== タイプ-1 ===
=== タイプ-2 ===
=== タイプ-3 ===
== 階層 ==
{| class="wikitable"
!チョムスキー階層
9 ⟶ 20行目:
|-
| タイプ-0
| [[制限なし文法|制限なし]]
| [[帰納的可算言語|帰納的可算]]
| [[チューリングマシン]]
|-
| n/a
|
| [[帰納言語|帰納]]
| Decider
|-
| タイプ-1
| [[文脈依存文法|文脈依存]]
| [[文脈依存言語|文脈依存]]
| [[線形拘束オートマトン|線形拘束]]
|-
| n/a
| Indexed ([[w:Indexed grammar|
| Indexed ([[w:Indexed language|
| Nested-stack ([[w:Nested stack automaton|
|-
| n/a
| [[木接合文法|木接合]]
| （[[弱文脈依存言語|弱文脈依存]]）
| Embedded Pushdown ([[w:Embedded pushdown automaton|
|-
| タイプ-2
| [[文脈自由文法|文脈自由]]
| [[文脈自由言語|文脈自由]]
| [[プッシュダウン・オートマトン|プッシュダウン]]
|-
| n/a
| 決定性文脈自由 ([[w:Deterministic context-free grammar|
| 決定性文脈自由 ([[w:Deterministic context-free language|
|
|-
| タイプ-3
| [[正規文法|正規]]
| [[正規言語|正規]]
| [[有限オートマトン|有限]]
|-
| n/a
|
| Star-free ([[w:Star-free language|
| Counter-Free
|-
| n/a
|
| Locally threshold-testable
|
|-
| n/a
|
| Locally testable
|
|-
| n/a
|
| Strictly local
| Scanners
|-
|}
== 参考文献 ==
* [http://ling.ed.ac.uk/~gpullum/MoL10paper.pdf |Rogers, James and Geoffrey K. Pullum (2007) Aural pattern recognition experiments and the subregular hierarchy. To appear in UCLA Working Papers in Linguistics: Mathematics of Language 10.]
78 ⟶ 91行目:
[[Category:文法]]
[[Category:理論計算機科学]]
{{language-stub}}
| |||