チョムスキー階層
Avram Noam Chomsky
が提案した形式文法のクラスを分類するための方法
0型
句構造文法
PSG
チューリングマシン
が認識できる全言語を生成できる
制限がない
1型
文脈依存文法
CSG
文脈依存言語を生成する
線形拘束オートマトン
生成規則
xAy → xuy
x,yは任意の記号列、Aは非終端記号、uは空でない記号列
2型
文脈自由文法
CFG
文脈自由言語を生成する
プッシュダウン・オートマトン
3型
正規文法
RG
有限オートマトン
例
正規表現
包含関係
0型
$ \supset
1型
$ \supset
2型
$ \supset
3型
https://ja.wikipedia.org/wiki/形式言語の階層
https://ja.wikipedia.org/wiki/チョムスキー階層
https://www.jstage.jst.go.jp/article/jssst/28/3/28_3_3_61/_pdf