形式言語理論とオートマトン

形式言語の理論と、それらを認識する抽象機械に関する学問分野であり、言語パターンがどれほど複雑であるか、またどのようなアルゴリズムがそれを処理できるかを記述するための語彙を提供する。

Definition

形式言語理論は文法によって定義される文字列の集合を研究し、オートマトン理論はそれらの集合への帰属を決定する抽象機械を研究する。

Scope

チョムスキー階層（正規言語、文脈自由言語、文脈依存言語、帰納的可算言語）、対応する文法、およびそれらを認識するオートマトン（有限オートマトン、プッシュダウンオートマトン、チューリングマシン）を扱う。言語処理に関連する閉包性および決定可能性の特性、ならびに自然言語が階層のどこに位置するかという問題にも触れる。ポンピング補題や完全な複雑性証明は、主要な内容ではなく背景として扱われる。

Core questions

• チョムスキー階層の各レベルにどのオートマトンが対応するか？
• 自然言語は階層のどこに位置し、なぜ文脈自由能力を超えると主張されるのか？
• 言語クラスがある操作の下で閉じているとはどういう意味か、そしてそれは工学にとってなぜ重要なのか？

Key concepts

• 正規言語
• 文脈自由文法
• 文脈依存文法
• 有限オートマトン
• プッシュダウンオートマトン
• チューリングマシン
• 閉包特性
• 弱文脈依存性

Key theories

チョムスキー階層

形式言語の4つの入れ子になったクラスであり、それぞれが制限された文法タイプによって生成され、対応するオートマトンによって認識され、必要な計算能力によって言語構造を順序付ける。

文法とオートマトンの対応

各文法クラスは機械クラスと証明可能に等価である。正規文法は有限オートマトンに、文脈自由文法はプッシュダウンオートマトンに対応し、生成記述と認識アルゴリズムを結びつける。

History

チョムスキーの1956年の論文は、有限状態モデルが自然言語には不十分であるという議論の一部として階層を導入した。その後の数十年でオートマトンの対応関係が形式化され、計算言語学者は後に自然言語がせいぜい「弱文脈依存」の能力を必要とすることを示し、文脈自由文法を超える文法形式を動機づけた。

Debates

自然言語は文脈自由か？

スイスドイツ語のような言語における交差依存関係は、自然言語が文脈自由能力を超えるという議論に用いられ、表現力の適切なレベルとして弱文脈依存性の概念につながった。

Key figures

• Noam Chomsky
• John Hopcroft
• Jeffrey Ullman
• Stephen Kleene

Seminal works

• chomsky1956
• hopcroft2006

Frequently asked questions

正規言語と文脈自由言語の違いは何か？

正規言語は有限オートマトンによって有限のメモリで認識できる。文脈自由言語は、括弧の対応や埋め込み節のような入れ子構造を追跡するためにスタック（プッシュダウンオートマトン）を必要とする場合がある。