チョムスキー階層
(サイエンス)
【ちょむすきーかいそう】
ノーム・チョムスキーが提案した形式文法のクラスを分類するための方法。
形式文法のクラスとは、簡単に言うとその文法によって生成される形式言語の複雑さのことで、以下の４つのタイプがある。
| タイプ | 文法 | 受理するオートマトン | 制限 |
|---|---|---|---|
| 0型 | 句構造文法 | チューリングマシン | なし |
| 1型 | 文脈依存文法 | 線形拘束オートマトン | αAβ→αγβ |
| 2型 | 文脈自由文法 | プッシュダウン・オートマトン | A→γ |
| 3型 | 正規文法 | 有限オートマトン | A→a または A→aB または A→Ba |
0型から3型に向かって、型の数字が大きくなるほど制限が増えていく。したがって、それぞれの型には「0型⊃1型⊃2型⊃3型」という包含関係がある。
形式言語の例
- 正規表現は3型の正規文法に分類される。
- ほとんどのプログラミング言語は2型の文脈自由文法で定義されている。
- 正確には形式言語ではないが、自然言語のモデルとしては1型の文脈依存文法程度で十分強力であると言われている。
ja.wikipedia.org