形式言語の階層

形式言語の包含階層はチョムスキー階層が知られているが、チョムスキーが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

• 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.