チョムスキー階層

チョムスキー階層は、形式言語を4つの入れ子になったクラスに分類するもので、それぞれが文法規則に対する制約によって定義され、異なる種類のアブストラクトマシンに対応しています。

Definition

チョムスキー階層は、形式文法をその生成規則に対する制約の段階的な強化によって分類するものであり、厳密な包含関係の連鎖において、正規言語、文脈自由言語、文脈依存言語、再帰的に可算言語のクラスを生み出します。

Scope

このトピックでは、非制限、文脈依存、文脈自由、正規の4つの文法タイプ、それらの厳密な包含関係、および各レベルに対応するオートマトンモデル（チューリングマシン、線形拘束オートマトン、プッシュダウンオートマトン、有限オートマトン）について、さらに各レベルを区別する閉包性と決定可能性の特性についても扱います。

Core questions

• 文法規則の制約は、メモリと計算能力の限界にどのように変換されるのか？
• なぜ階層の各レベルは次のレベルに厳密に含まれるのか？
• 各文法タイプに対応するオートマトンモデルは何か？
• 階層を上がるにつれて、決定可能性と閉包特性はどのように変化するのか？

Key theories

文法と機械の対応関係

各文法クラスは特定の機械モデルによって認識されます。正規言語は有限オートマトン、文脈自由言語はプッシュダウンオートマトン、文脈依存言語は線形拘束オートマトン、非制限言語はチューリングマシンによって認識され、これにより計算の生成記述と操作記述が結びつけられます。

言語クラスの厳密な包含関係

各レベルは、具体的な分離言語によって示されるように、その下のレベルを適切に含んでいます。したがって、この階層は同等の記述の集合ではなく、表現能力が増大する真の段階を示しています。

Clinical relevance

この階層は形式言語理論の組織的な地図であり、プログラミング言語、クエリ言語、プロトコル仕様の設計者に対し、特定のパターンのクラスがどの程度の機構を必要とするかを示し、何が決定可能で何が認識可能であるかの境界を明確にします。

History

チョムスキーは1950年代後半に自然言語の構文の形式モデルを模索する中でこの階層を提案し、1960年代にオートマトン理論が成熟するにつれて機械との対応関係が確立されました。線形拘束オートマトンはMyhillによって導入され、文脈依存レベルはKurodaによって明確化されました。

Key figures

• Noam Chomsky
• Marcel-Paul Schützenberger
• John Myhill

Seminal works

• hopcroft2006
• sipser2013

Frequently asked questions

チョムスキー階層の4つのレベルとは何ですか？

能力の低い順に、正規言語（タイプ3）、文脈自由言語（タイプ2）、文脈依存言語（タイプ1）、再帰的に可算言語（タイプ0）です。各レベルは文法規則に対する制約を緩和し、より多くのメモリを持つ機械に対応します。

自然言語はチョムスキー階層によって捉えられますか？

この階層は元々言語学によって動機づけられましたが、ほとんどの言語学者は自然言語は文脈自由ではなく、しばしば「やや文脈依存的」と呼ばれるレベルに位置すると結論付けています。人間言語がこの階層に厳密には当てはまらないとしても、この階層はコンピュータサイエンスにおいて依然として基礎的なものです。