文脈自由言語

文脈自由言語とは

文脈自由言語とは、特定の生成規則を持つ形式言語の一種です。このような言語は、与えられた言語の長さ n に対して O(n³) の時間で認識することができ、プッシュダウン・オートマトンにより受理可能な言語と同等です。

基本的な生成規則

文脈自由言語は、以下のように表現される生成規則によって形成されます。具体例として、次の文法 S → E が挙げられます。ここで E は算術演算や括弧による式を表します。文法は以下のように定義されます。

• - S → E。
• - E → T | E - T | E + T | (E)。
• - T → T * E | T / E | id | num。

この生成規則は、数式やプログラミング言語における文法を構成する際に広く使用されます。

文脈自由言語の例

例えば、文字列の言語 L = {aⁿbⁿ: n ≥ 1} は文脈自由言語の一例です。この言語は、前半が a で構成され、後半が b で構成された、偶数の文字からなる文字列で構成されています。この言語の文法は S → aSb | ab で表現できます。また、この言語はプッシュダウン・オートマトンによって受理されることが確認されています。

文脈自由言語の閉包属性

文脈自由言語にはいくつかの閉包属性があります。例えば、ある文脈自由言語 L と正規言語 D が与えられた場合、以下の操作もまた文脈自由言語になります。

1. L のクリーネ閉包 L⁗
2. L の準同型 φ(L)
3. L と P の連結 L ∘ P
4. L と P の和集合 L ∪ P
5. L と正規言語 D の積集合 L ∩ D

ただし、積集合や差集合に関しては文脈自由言語が閉じていないことに注意する必要があります。特に、積集合に関しての詳細は、形式言語に関する文献を参照してください。

積集合に関する証明

文脈自由言語が積集合に対して閉じていないことを示すために、具体的な例として二つの文脈自由言語 A と B を取り上げます。 A = {a^m b^n c^n | m, n ≥ 0} と B = {a^n b^n c^m | m, n ≥ 0} です。この二つの言語の積集合 A ∩ B は {a^n b^n c^n | n ≥ 0} であり、文脈自由言語の反復補題を用いることで、この集合が文脈自由言語でないことを示すことができます。

決定性属性

文脈自由言語に関するいくつかの問題は決定不能です。例えば、与えられた二つの文脈自由文法 A と B が等価かどうかを判断する問題や積集合が空であるかどうかを判断する問題などが挙げられます。これに対し、メンバーシップ問題、すなわち特定の単語が言語に含まれるかどうかは、決定可能です。

参考文献

この文に関する詳細は、Michael Sipser の「Introduction to the Theory of Computation」に記載されており、特に第2章では文脈自由言語の理論について詳しく説明されています。

もう一度検索