「形式言語の階層」の版間の差分

削除された内容追加された内容

インライン

2008年5月3日 (土) 23:11時点における版

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

2008年5月3日 (土) 23:07時点における版編集ペー (会話 \| 投稿記録) 311 回編集編集の要約なし ← 古い編集		2008年5月3日 (土) 23:11時点における版編集取り消しペー (会話 \| 投稿記録) 311 回編集 m編集の要約なし新しい編集 →
73行目:		73行目:

	== Reference ==		== Reference ==
	* [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.]		* [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.]