チョムスキー階層

チョムスキー階層

チョムスキー階層（Chomsky hierarchy）は、形式言語を生成する文法の構造を明らかにするための分類法であり、1956年にノーム・チョムスキーによって提唱されました。この階層は、形式文法の特性に基づいて4つの主要なタイプに分類され、各タイプは異なる性質の言語を生成可能です。ここでは、それぞれの文法タイプの特徴とその階層的関係について詳しく解説します。

形式文法とは

形式文法は、特定の規則に従って文字列を生成する体系です。これには、以下の要素が含まれます：

• - 終端記号（Terminal Symbols）: 実際に使用される文字の集合。
• - 非終端記号（Nonterminal Symbols）: 文法内で派生するための記号の集合。
• - 生成規則（Production Rules）: 非終端記号を他の記号列に置換するためのルール。
• - 開始記号（Start Symbol）: 生成過程の出発点となる記号。

このように、開始記号から生成規則を適用していくことで、最終的に終端記号だけからなる文字列を構築します。たとえば、非終端記号Sから生成される言語の例には、n個のaの後にn個のbが続く形式の言語（a^n b^n）が存在します。

チョムスキー階層

チョムスキー階層は、以下の4つのレベルから構成されています。これらは、生成する言語の特性や、対応するオートマトンの種類に基づいています。

タイプ-0 文法

タイプ-0文法は、最大限の自由度を持つ制約のない文法であり、全ての形式文法を含みます。この文法はチューリングマシンが認識できる全ての言語を生成でき、帰納的可算言語として知られています。これに対して、チューリングマシンが必ず停止して判定可能な言語は帰納言語と呼ばれ、これらは異なる特性を持っています。

タイプ-1 文法

タイプ-1文法は、文脈依存文法であり、文脈によって生成規則が変化します。この文法は、生成規則が$
\alpha A \beta \rightarrow \alpha \gamma \beta
$という形を持ち、ここでAは非終端記号、$
\alpha,
\beta,
\gamma
$は終端記号と非終端記号からなる文字列です。この文法で記述される言語は、線形拘束オートマトンによって認識されます。

タイプ-2 文法

タイプ-2文法は文脈自由文法で、文脈に依存しない規則を持ちます。生成規則の形式は$
A \rightarrow \gamma
$であり、Aは非終端記号、$
\gamma
$は文字列です。この文法を用いて生成される言語は、非決定性プッシュダウンオートマトンによって認識され、プログラミング言語の文法としても一般的に使用されています。

タイプ-3 文法

タイプ-3文法は正規文法であり、生成規則は左側に必ず一つの非終端記号と、右側には一つの終端記号が含まれます。この文法が生成する言語群は有限オートマトンによって判定され、正規表現の形成に広く利用されています。

階層的関係

このチョムスキー階層の重要な点は、各文法の種類間に真の包含関係が存在することです。つまり、すべての正規文法は文脈自由文法に含まれ、文脈自由文法は文脈依存文法に含まれ、その文脈依存文法は帰納言語に、そして帰納言語は帰納的可算言語に含まれます。この階層構造は、言語の複雑さや計算能力に関連して、言語理論や情報理論に大きな影響を与えています。

参考文献

• - Chomsky, Noam (1956). "Three models for the description of language".
• - Chomsky, Noam (1959). "On certain formal properties of grammars".
• - Chomsky, Noam; Schützenberger, Marcel P. (1963). "The algebraic theory of context free languages".

もう一度検索