文脈に依存しない言語

形式言語理論において、 文脈自由言語( CFL ) は、チョムスキー型 2 言語とも呼ばれ、文脈自由文法( CFG ) によって生成される言語です。

文脈自由言語はプログラミング言語において多くの用途があり、特にほとんどの算術式は文脈自由文法によって生成されます。

異なる文脈自由文法から、同じ文脈自由言語を生成できます。言語を記述する複数の文法を比較することで、言語の固有の特性と特定の文法の外部特性を区別できます。

すべての文脈自由言語の集合は、プッシュダウンオートマトンが受け入れる言語の集合と同一であり、これにより、これらの言語は構文解析可能になります。さらに、与えられた CFG に対して、文法 (および対応する言語) のプッシュダウンオートマトンを直接生成する方法がありますが、逆の方法 (オートマトンが与えられた場合に文法を生成する) はそれほど直接的ではありません。

文脈自由言語の例としては、空でない偶数長の文字列すべてからなる言語である が挙げられ、その前半全体がaで、後半全体がbである。Lは文法 によって生成される。この言語は正規のではない。これはプッシュダウンオートマトンによって受け入れられ、 は次のように定義される: ^{[注 1]}${\displaystyle L=\{a^{n}b^{n}:n\geq 1\}}$${\displaystyle S\to aSb~|~ab}$ ${\displaystyle M=(\{q_{0},q_{1},q_{f}\},\{a,b\},\{a,z\},\delta ,q_{0},z,\{q_{f}\})}$${\displaystyle \delta}$

${\displaystyle {\begin{aligned}\delta (q_{0},a,z)&=(q_{0},az)\\\delta (q_{0},a,a)&=(q_{0},aa)\\\delta (q_{0},b,a)&=(q_{1},\varepsilon )\\\delta (q_{1},b,a)&=(q_{1},\varepsilon )\\\delta (q_{1},\varepsilon ,z)&=(q_{f},\varepsilon )\end{aligned}}}$

曖昧でない CFL はすべての CFL の適切な部分集合です。本質的に曖昧なCFL も存在します。本質的に曖昧な CFL の例としては、と の和集合が挙げられます。2 つの文脈自由言語の和集合は常に文脈自由であるため、この集合は文脈自由です。しかし、これら 2 つの言語の共通部分である (文脈自由でない) 部分集合内の文字列を曖昧でない方法で解析する方法はありません。^[1]${\displaystyle \{a^{n}b^{m}c^{m}d^{n}|n,m>0\}}$${\displaystyle \{a^{n}b^{n}c^{m}d^{m}|n,m>0\}}$${\displaystyle \{a^{n}b^{n}c^{n}d^{n}|n>0\}}$

適切に対応したすべての括弧の言語は文法によって生成されます。 ${\displaystyle S\to SS~|~(S)~|~\varepsilon }$

言語の文脈自由性により、プッシュダウンオートマトンによる解析が簡単になります。

所属問題のインスタンスの判定、つまり文字列 が与えられたときに、が与えられた文法によって生成された言語 であるかどうかを判定することは、認識とも呼ばれます。チョムスキー標準形文法の文脈自由認識は、 Leslie G. Valiantによってブール行列乗算に還元可能であることが示され、したがってその複雑性の上限O ( n ^2.3728596 ) を継承します。^{[2] [注 2]} 逆に、Lillian Lee は、O ( n ^3−ε ) のブール行列乗算がO ( n ^3−3ε ) の CFG 構文解析 に還元可能であることを示しており、後者のある種の下限を確立しています。^[3]${\displaystyle w}$${\displaystyle w\in L(G)}$${\displaystyle L}$${\displaystyle G}$

文脈自由言語を実際に使用するには、文法が特定の文字列に関連付ける構造を示す導出ツリーを生成することも必要です。このツリーを生成するプロセスは、解析と呼ばれます。既知のパーサーには、解析される文字列のサイズの 3 乗の時間計算量があります。

正式には、すべての文脈自由言語の集合は、プッシュダウンオートマトン (PDA) によって受け入れられる言語の集合と同一です。文脈自由言語のパーサー アルゴリズムには、CYK アルゴリズムやEarley のアルゴリズムなどがあります。

文脈自由言語の特別なサブクラスとして決定性文脈自由言語があり、これは決定性プッシュダウンオートマトンによって受け入れられ、 LR(k)パーサによって解析できる言語の集合として定義されます。^[4]

文法とパーサーの代替アプローチとして、 式文法の解析も参照してください。

文脈自由言語のクラスは、次の操作に対して閉じています。つまり、LとP が文脈自由言語である場合、次の言語も文脈自由言語です。

• LとPの結合 [ ⁵ ]${\displaystyle L\cup P}$
• Lの反転^[6]
• LとPの連結^[5 ] ${\displaystyle L\cdot P}$
• Lのクリーネ星 [ ^5]${\displaystyle L^{*}}$
• Lの準同型写像^[7]${\displaystyle \varphi (L)}$ ${\displaystyle \varphi}$
• 逆準同型によるLの像^[8]${\displaystyle \varphi ^{-1}(L)}$ ${\displaystyle \varphi^{-1}}$
• L（言語）の循環シフト^[9]${\displaystyle \{vu:uv\in L\}}$
• Lの接頭辞閉包（ Lの文字列のすべての接頭辞の集合）^[10]
• Lを正規言語Rで割った商 L / R [ ^11]

文脈自由言語は、共通部分について閉じていない。これは、両方とも文脈自由である言語とをとればわかる。 ^{[注 3]}それらの共通部分は であり、これは文脈自由言語 のポンピング補題によって非文脈自由であることが示される。結果として、文脈自由言語は補集合について閉じることができない。なぜなら、任意の言語AとBについて、それらの共通部分は和集合と補集合で表現できるからである: 。特に、文脈自由言語は差集合について閉じることができない。なぜなら、補集合は差集合で表現できるからである: 。^[12]${\displaystyle A=\{a^{n}b^{n}c^{m}\mid m,n\geq 0\}}$${\displaystyle B=\{a^{m}b^{n}c^{n}\mid m,n\geq 0\}}$${\displaystyle A\cap B=\{a^{n}b^{n}c^{n}\mid n\geq 0\}}$${\displaystyle A\cap B={\overline {{\overline {A}}\cup {\overline {B}}}}}$${\displaystyle {\overline {L}}=\Sigma ^{*}\setminus L}$

しかし、Lが文脈自由言語でDが正規言語である場合、それらの共通部分と相違部分は両方とも文脈自由言語である。^[13]${\displaystyle L\cap D}$${\displaystyle L\setminus D}$

形式言語理論では、正規言語に関する質問は通常は決定可能ですが、文脈自由言語に関する質問は決定できないことがよくあります。そのような言語が有限であるかどうかは決定可能ですが、すべての可能な文字列が含まれているかどうか、正規であるかどうか、曖昧さがないかどうか、または異なる文法を持つ言語と同等であるかどうかは決定できません。

次の問題は、任意に与えられた文脈自由文法A と B では決定不可能です。

• 同値性: ですか? ^[14]${\displaystyle L(A)=L(B)}$
• 分離性: は ? ^[15]しかし、文脈自由言語と正規言語の交差は文脈自由である。^{[16] [17]したがって、} Bが正規文法である問題の変形は決定可能である(下記の「空」を参照)。${\displaystyle L(A)\cap L(B)=\emptyset }$
• 包含: ですか ? ^{[18]繰り返しますが、} Bが正規文法である場合の問題の変形は決定可能ですが^{[引用が必要]、}Aが正規である場合の問題の変形は一般に決定できません。^[19]${\displaystyle L(A)\subseteq L(B)}$
• 普遍性：？^[20]${\displaystyle L(A)=\Sigma ^{*}}$
• 規則性：正規言語か？^[21]${\displaystyle L(A)}$
• 曖昧さ：すべての文法は曖昧なのか？^[22]${\displaystyle L(A)}$

任意の文脈自由言語に対して、 以下の問題が決定可能です。

• 空: 文脈自由文法Aが与えられたとき、空であるか ？^[23]${\displaystyle L(A)=\emptyset }$
• 有限性：文脈自由文法Aが与えられたとき、それは有限であるか？^[24]${\displaystyle L(A)}$
• メンバーシップ: 文脈自由文法Gと単語が与えられたとき、 となるでしょうか ? メンバーシップ問題に対する効率的な多項式時間アルゴリズムは、CYK アルゴリズムとEarley のアルゴリズムです。${\displaystyle w}$${\displaystyle w\in L(G)}$

ホップクロフト、モトワニ、ウルマン（2003）^{[25]によれば、文脈自由言語の基本的な閉包性と（非）決定可能性の多くは、1961年の}バー・ヒレル、パールズ、シャミール の論文^{[26]で示された。}

この集合は文脈依存言語であるが、この言語を生成する文脈自由文法は存在しない。^[27]そのため、文脈自由ではない文脈依存言語が存在する。与えられた言語が文脈自由でないことを証明するには、文脈自由言語に対するポンピング補題^[26]や、オグデンの補題やパリクの定理など他のいくつかの方法を使うことができる。^[28]${\displaystyle \{a^{n}b^{n}c^{n}d^{n}|n>0\}}$

• Autebert, Jean-Michel; Berstel, Jean; Boasson, Luc (1997). 「文脈自由言語とプッシュダウンオートマトン」。G. Rozenberg、A. Salomaa (編)。形式言語ハンドブック(PDF)。第 1 巻。Springer-Verlag。pp. 111–174。2011-05-16にオリジナルからアーカイブ(PDF) 。
• ギンズバーグ、シーモア(1966)。文脈自由言語の数学的理論。ニューヨーク、ニューヨーク、アメリカ合衆国:マグロウヒル。
• Sipser, Michael (1997)。「2 : 文脈自由言語」。計算理論入門(第 1 版)。PWS Publishing。91 ～ 122 ページ。ISBN 978-0-534-94728-6。（印刷障害のある利用者も利用可能）