形式言語理論 (Formal Language Theory)

チョムスキー階層に関わる形式言語理論。

---

前回の投稿で、チョムスキー階層(Chomsky hierarchy) というものを紹介した。

この階層は言語の複雑性によって下記の4段階のレベルを持つ。

今回はこの階層分類の基幹になる形式言語理論について触れる。

1. 有限オートマトン (finite automaton)
   正則文法 (regular grammar)
2. プッシュダウン・オートマトン (pushdown automaton)
   文脈自由文法 (context-free grammar)
3. 線形拘束オートマトン (linear bounded automaton)
   文脈依存文法 (context-sensitive grammar)
4. チューリング機械 (Turing Machine)
   句構造文法 (phrase structure grammar)

(北 1999)

この階層の前提はまず（Chomsky らしく）意味を無視していることに留意したい。意味を捨象することで言語を純粋な文字列の集合として扱うことができるようになる。このように言語を形式化して扱う理論のことを形式言語理論（Formal Language Theory、FLT）と呼ぶ。

この形式化により言語を記号の配列の集合と捉えることが可能になる。

この発想の功績は非常に大きく、言語学だけでなく分子生物学や現代の コンピューターサイエンスの自然、言語処理の分野において、非常に大きい影響を及ぼした。

参考文献

• 北研二. (1999). 確率的言語モデル. 言語と計算, 4.
• Chomsky, N. (1956). Three models for the description of language. IRE Transactions on information theory, 2(3), 113-124.
• Jäger, G., & Rogers, J. (2012). Formal language theory: refining the Chomsky hierarchy. Philosophical Transactions of the Royal Society B: Biological Sciences, 367(1598), 1956-1970.