投稿者: 
4種類に分類される言語。
言語というと我々は日本語や英語のようないわゆる「自然言語」を思い浮かべることが一般的である。しかし、コンピュータの発達に伴って「プログラミング言語」等も発展してきていることは周知の通りである。
ここで我々の自然言語とコンピュータのプログラミング言語を比べてみよう。
自然言語：私はお寿司を食べる。
プログラミング言語：print(“Hello World”)
自然言語は例えば「お寿司を私は食べる」というように語順を変えることもできるが、プログラミング言語は自然言語に比べて厳密に構造が定まっており、こういった語順の入れ替えはできない。このように考えてみると自然言語とプログラミング言語では言語の複雑性が異なることがわかる。
このように言語は複雑性のレベルというものが存在する。チョムスキーはこういった複雑性の観点から4つの階層に分類した。
- 有限オートマトン (finite automaton)
正則文法 (regular grammar) - プッシュダウン・オートマトン (pushdown automaton)
文脈自由文法 (context-free grammar) - 線形拘束オートマトン (linear bounded automaton)
文脈依存文法 (context-sensitive grammar) - チューリング機械 (Turing Machine)
句構造文法 (phrase structure grammar)
(北 1999)
1に分類されるものほど簡易な記述能力しか持たず、4が最も複雑な記述能力を持つ。
この階層をチョムスキーの名を取ってチョムスキー階層と呼ぶ。
参考文献
- 北研二. (1999). 確率的言語モデル. 言語と計算, 4.
- Chomsky, N. (1956). Three models for the description of language. IRE Transactions on information theory, 2(3), 113-124.