文脈自由文法

形式言語理論において、文脈自由文法（CFG）とは、文脈に関係なく非終端記号 に適用できる生成規則を持つ形式文法である。特に、文脈自由文法では、各生成規則は次の形式である。

${\displaystyle A\ \to \ \alpha }$

単一の非終端記号と、終端記号および/または非終端記号の文字列 (は空でも可) で構成されます。 周囲の記号に関係なく、左側の単一の非終端記号は、常に右側の に置き換えることができます。 この点が、非終端記号と、、、および終端記号および/または非終端記号の文字列で 構成される という形式の生成規則を持つことができる文脈依存文法との違いです。${\displaystyle A}$${\displaystyle \alpha }$${\displaystyle \alpha }$${\displaystyle A}$${\displaystyle \alpha }$${\displaystyle \alpha A\beta \rightarrow \alpha \gamma \beta }$${\displaystyle A}$${\displaystyle \alpha }$${\displaystyle \beta }$${\displaystyle \gamma }$

形式文法は、本質的には、与えられた形式言語におけるすべての可能な文字列を記述する生成規則の集合である。生成規則は単純な置換である。例えば、図の最初の規則は、

${\displaystyle \langle {\text{Stmt}}\rangle \to \langle {\text{Id}}\rangle =\langle {\text{Expr}}\rangle ;}$

を に置き換えます。特定の非終端記号には複数の置換規則がある場合があります。文法によって生成される言語は、規則を繰り返し適用することで、特定の非終端記号 (「開始記号」) から導出できる終端記号のすべての文字列のセットです。非終端記号は導出プロセス中に使用されますが、最終結果の文字列には表示されません。 ${\displaystyle \langle {\text{Stmt}}\rangle }$${\displaystyle \langle {\text{Id}}\rangle =\langle {\text{Expr}}\rangle ;}$

文脈自由文法によって生成される言語は、文脈自由言語(CFL) として知られています。異なる文脈自由文法から、同じ文脈自由言語が生成されることがあります。言語の特性 (固有の特性) と特定の文法の特性 (外部特性) を区別することが重要です。言語の等価性に関する質問 (2 つの文脈自由文法から同じ言語が生成されるかどうか) は、決定不可能です。

文脈自由文法は言語学で生まれ、自然言語の文や単語の構造を記述するために使用され、言語学者ノーム・チョムスキーがこの目的のために発明しました。対照的に、コンピュータサイエンスでは、再帰的に定義された概念の使用が増えるにつれて、文脈自由文法がますます使用されるようになりました。初期のアプリケーションでは、文法はプログラミング言語の構造を記述するために使用されます。より新しいアプリケーションでは、文法は拡張マークアップ言語（XML）のドキュメント型定義と呼ばれる重要な部分で使用されます。^[2]

言語学では、文脈自由文法を指すのに句構造文法という用語を使用する著者もいますが、句構造文法は依存文法とは区別されます。コンピューターサイエンスでは、文脈自由文法の一般的な表記法はバッカス・ナウア記法、つまり BNF です。

少なくとも古代インドの学者パーニニの時代から、言語学者は言語の文法をブロック構造の観点から説明し、文が小さな句から、そして最終的には個々の単語または単語要素から再帰的に構築される方法を説明してきました。これらのブロック構造の重要な特性は、論理単位が決して重複しないことです。たとえば、次の文:

ガレージに青い車を置いていたジョンは、食料品店まで歩いて行きました。

次のように論理的に括弧で囲むことができます（論理メタ記号[ ]を使用）。

[ジョン[、[青い車]] [が[ガレージ]]にあった ] ] [は[食料品店] ] ]まで歩いて行きました。

文脈自由文法は、自然言語の句が小さなブロックから構築される方法を記述するための単純で数学的に正確なメカニズムを提供し、文の「ブロック構造」を自然な方法で捉えます。その単純さにより、形式論は厳密な数学的研究に適しています。一致や参照などの自然言語構文の重要な特徴は文脈自由文法の一部ではありませんが、文の基本的な再帰構造、節が他の節の中にネストされる方法、形容詞と副詞のリストが名詞と動詞に飲み込まれる方法は正確に記述されます。

文脈自由文法はセミ・トゥー・システムの特殊な形式であり、その一般的な形式はアクセル・トゥーの研究にまで遡ります。

文脈自由文法の形式主義は、1950年代半ばにノーム・チョムスキーによって開発され、^[3]特別な種類の形式文法（チョムスキーはこれを句構造文法と呼んだ）としての分類もなされた。 ^[4]しかし、一部の著者は、この用語をチョムスキー階層のより限定された文法、すなわち文脈依存文法または文脈自由文法のために留保している。より広い意味では、句構造文法は構成文法とも呼ばれる。句構造文法の特徴は、従属関係の依存文法とは対照的に、構成関係に従うことである。チョムスキーの生成文法フレームワークでは、自然言語の構文は、文脈自由規則と変換規則の組み合わせによって記述された。^[5]

ブロック構造は、アルゴルプロジェクト (1957-1960)によってコンピュータプログラミング言語に導入され、その結果、アルゴル構文を記述するための文脈自由文法^{[6]も採用されました。これはコンピュータ言語の標準機能となり、コンピュータ言語の具体的な記述に使用される文法の表記は、アルゴル言語設計委員会の 2 人のメンバーにちなんで、}バッカス-ナウア記法として知られるようになりました。^[3]文脈自由文法が捉える「ブロック構造」の側面は、文法にとって非常に基本的なため、特にコンピュータ サイエンスでは、構文と文法という用語は、文脈自由文法の規則と同一視されることがよくあります。文法によって捉えられない形式的な制約は、言語の「意味論」の一部と見なされます。

文脈自由文法は、与えられた文字列が文法から生成できるかどうか、またどのように生成できるかを判断する効率的な解析アルゴリズムを構築できるほど単純です。Earleyパーサーはそのようなアルゴリズムの一例ですが、広く使用されているLRパーサーとLL パーサーは、文脈自由文法のより制限されたサブセットのみを扱うより単純なアルゴリズムです。

文脈自由文法Gは4つの組 で定義され、^[a]${\displaystyle G=(V,\Sigma ,R,S)}$

1. Vは有限集合です。各要素は非終端文字または変数と呼ばれます。各変数は文中の異なる種類の句または節を表します。変数は統語カテゴリと呼ばれることもあります。各変数はGによって定義された言語のサブ言語を定義します。${\displaystyle v\in V}$
2. Σ は、Vとは独立し、文の実際の内容を構成している終端記号の有限集合です。終端記号の集合は、文法Gによって定義された言語のアルファベットです。
3. R はにおける有限関係であり、アスタリスクはクリーネスター演算を表します。R の要素は、文法の(書き換え) 規則または生成規則と呼ばれます。(一般的にPで表されます)${\displaystyle V\times (V\cup \Sigma )^{*}}$
4. S は開始変数（または開始シンボル）であり、文全体（またはプログラム）を表すために使用されます。これはVの要素である必要があります。

Rの生成規則は、数学的にはペア として形式化されます。ここで、は非終端記号、 は変数および/または終端記号の文字列です。順序付きペア表記を使用するのではなく、生成規則は通常、矢印演算子を使用して、その左側に 、右側に β を使用して記述されます。 ${\displaystyle (\alpha ,\beta )\in R}$${\displaystyle \alpha \in V}$${\displaystyle \beta \in (V\cup \Sigma )^{*}}$${\displaystyle \alpha }$${\displaystyle \alpha \rightarrow \beta }$

βが空文字列であることも許されており、この場合にはεで表記するのが通例である。この形式はε生成と呼ばれる。^[7]${\displaystyle \alpha \rightarrow \varepsilon }$

同じ左辺に対するすべての右辺を、| (縦棒)を使用して区切って同じ行にリストするのが一般的です。規則および は、したがって と記述できます。この場合、およびは、それぞれ第 1 および第 2 の選択肢と呼ばれます。 ${\displaystyle \alpha \rightarrow \beta _{1}}$${\displaystyle \alpha \rightarrow \beta _{2}}$${\displaystyle \alpha \rightarrow \beta _{1}\mid \beta _{2}}$${\displaystyle \beta _{1}}$${\displaystyle \beta _{2}}$

任意の文字列 に対して、 かつでかつとなる場合、u はと表記されるv を直接生成するといいます。したがって、v はuに規則を適用した結果です。 ${\displaystyle u,v\in (V\cup \Sigma )^{*}}$${\displaystyle u\Rightarrow v\,}$${\displaystyle \exists (\alpha ,\beta )\in R}$${\displaystyle \alpha \in V}$${\displaystyle u_{1},u_{2}\in (V\cup \Sigma )^{*}}$${\displaystyle u\,=u_{1}\alpha u_{2}}$${\displaystyle v\,=u_{1}\beta u_{2}}$${\displaystyle (\alpha ,\beta )}$

任意の文字列について、となる正の整数kと文字列が存在する場合、u はv を生成する、またはvはuから導出されると言います。この関係は、一部の教科書では、または と表記されます。 の場合、関係は成立します。言い換えると、 および は、それぞれの反射推移閉包（文字列がそれ自体を生成することを可能にする）および推移閉包（少なくとも 1 つのステップを必要とする）です。 ${\displaystyle u,v\in (V\cup \Sigma )^{*},}$ ${\displaystyle u_{1},\ldots ,u_{k}\in (V\cup \Sigma )^{*}}$${\displaystyle u=u_{1}\Rightarrow u_{2}\Rightarrow \cdots \Rightarrow u_{k}=v}$${\displaystyle u{\stackrel {*}{\Rightarrow }}v}$${\displaystyle u\Rightarrow \Rightarrow v}$${\displaystyle k\geq 2}$${\displaystyle u{\stackrel {+}{\Rightarrow }}v}$${\displaystyle ({\stackrel {*}{\Rightarrow }})}$${\displaystyle ({\stackrel {+}{\Rightarrow }})}$${\displaystyle (\Rightarrow )}$

文法の言語は集合である ${\displaystyle G=(V,\Sigma ,R,S)}$

${\displaystyle L(G)=\{w\in \Sigma ^{*}:S{\stackrel {*}{\Rightarrow }}w\}}$

開始記号から導出可能なすべての終端記号文字列。

言語Lが文脈自由言語 (CFL) であるとは、となるCFG G が存在する場合を指します。 ${\displaystyle L\,=\,L(G)}$

非決定性プッシュダウンオートマトンでは、文脈自由言語を正確に認識します。

文法と生成 ${\displaystyle G=(\{S\},\{a,b\},P,S)}$

S → aSa、

S → bSb、

S → ε、

は文脈自由である。ε生成を含んでいるので適切ではない。この文法における典型的な導出は

S → aSa → aaSaa → aabSbaa → aabbaa。

これにより、 であることが明らかになります 。言語は文脈自由ですが、正規ではないことが証明できます。 ${\displaystyle L(G)=\{ww^{R}:w\in \{a,b\}^{*}\}}$

作品が

S → a、

S → b、

を加えると、アルファベット{ a , b }上のすべての回文の集合に対する文脈自由文法が得られる。^[8]

文脈自由文法の標準的な例は括弧のマッチングであり、これは一般的なケースの代表である。2つの終端記号「(」と「)」と1つの非終端記号Sがある。生成規則は次の通りである。

S → SS、

S → ( S )、

さ→ ()

最初のルールはSシンボルの乗算を許可し、2番目のルールはSシンボルが対応する括弧で囲まれることを許可し、3番目のルールは再帰を終了します。^[9]

2 番目の標準的な例は、次の生成規則で記述される 2 種類の対応するネストされた括弧です。

S → SS

さ→ ()

S → ( S )

そ→ []

さ→ [さ]

終端記号は[]()、非終端記号はSです。

この文法では次のシーケンスを導き出すことができます。

([ [ [ ()() [ ][ ] ] ]([ ]) ])

文脈自由文法では、括弧と同じように文字をペアにすることができます。最も簡単な例:

S → aSb

S → アブ

この文法は言語 を生成しますが、これは正規言語 のポンピング補題によれば正規ではありません。 ${\displaystyle \{a^{n}b^{n}:n\geq 1\}}$

特殊文字εは空文字列を表します。上記の文法を次のように変更すると、

S → aSb

S → ε

代わりに、言語を生成する文法が得られます。これは、元の文法には含まれていなかった空の文字列が含まれているという点だけが異なります。 ${\displaystyle \{a^{n}b^{n}:n\geq 0\}}$

{a,b} 上のすべての文字列のうち、a と b の数が等しくないものから構成される言語の文脈自由文法:

S → T | U

T → VaT | VaV | TaV

U → VbU | VbV | UbV

V → aVbV | bVaV | ε

ここで、非終端記号 T は、a の数が b の数よりも多いすべての文字列を生成でき、非終端記号 U は、b の数が a の数よりも多いすべての文字列を生成し、非終端記号 V は、a と b の数が等しいすべての文字列を生成します。T と U の規則で 3 番目の選択肢を省略しても、文法の言語は制限されません。

非正規言語のもう 1 つの例は です。これは、次の文脈自由文法によって生成できるため、文脈自由です。 ${\displaystyle \{{\text{b}}^{n}{\text{a}}^{m}{\text{b}}^{2n}:n\geq 0,m\geq 0\}}$

S → bSbb | A

A → aA | ε

形式論理の用語と式の形成規則は、記号の集合が無限であり、開始記号が複数存在する可能性があることを除いて、文脈自由文法の定義に適合します。

前のセクションの適切に形成されたネストされた括弧と角括弧とは対照的に、2 つの異なるタイプの括弧のすべてのシーケンスを生成するための文脈自由文法は存在しません。これらの括弧は、それぞれが他方を無視して個別にバランスが取られており、2 つのタイプが互いにネストする必要はありません。次に例を示します。

[ ( ] )

または

[ [ [ (((( ] ] ]))))(([ ))(([ ))([ )( ])( ])( ])

この言語が文脈自由でないことは、文脈自由言語のポンピング補題と背理法を用いて証明することができ、形式のすべての単語は 言語に属するはずであることを観察する。この言語は、代わりにより一般的なクラスに属し、接続文法によって記述することができ、接続文法には、形式のすべての単語の言語など、他の非文脈自由言語も含まれる 。 ${\displaystyle {(}^{n}{[}^{n}{)}^{n}{]}^{n}}$${\displaystyle {\text{a}}^{n}{\text{b}}^{n}{\text{c}}^{n}}$

すべての正規文法は文脈自由文法ですが、すべての文脈自由文法が正規文法であるわけではありません。^[10]たとえば、次の文脈自由文法も正規文法です。

S →ア

S → aS

S → bS

ここでの終端はaとbですが、非終端はSのみです。記述されている言語は、で終わるs とs の空でないすべての文字列です。 ${\displaystyle a}$${\displaystyle b}$${\displaystyle a}$

この文法は正規です。つまり、どの規則も右側に複数の非終端記号を持たず、これらの各非終端記号は右側の同じ端にあります。

すべての正規文法は非決定性有限オートマトンに直接対応するので、これが正規言語であることがわかります。

縦棒を使用すると、上記の文法は次のように簡潔に記述できます。

S → a | aS | bS

文法の文字列の導出は、開始記号を文字列に変換する一連の文法規則の適用です。導出により、文字列が文法の言語に属していることを証明します。

導出は、各ステップごとに以下を与えることで完全に決定されます。

• そのステップで適用されたルール
• それが適用される左側の出現

わかりやすくするために、通常は中間文字列も示されます。

たとえば、文法は次のようになります。

1. S → S + S
2. ス→1
3. S →ア

文字列

1 + 1 + a

開始記号Sから次の導出によって 導出できる。

S

→ S + S （ Sの規則 1. による）

→ S + S + S （ルール1により、2番目のSについて）

→ 1 + S + S （ルール2により、最初のSについて）

→ 1 + 1 + S （ルール2. 2番目のSによる）

→ 1 + 1 + a（ルール3. 3番目のSによる）

多くの場合、次の非終端記号を決定論的に選択して書き換える戦略が採用されます。

• 最左導出では、常に最左の非終端記号になります。
• 最右導出では、常に最右の非終端記号になります。

このような戦略では、導出は適用される規則の順序によって完全に決定される。例えば、同じ文字列の左端の導出の1つは、

S

→ S + S（左端のSのルール1による）

→ 1 + S（左端のSのルール2による）

→ 1 + S + S（左端のSのルール1による）

→ 1 + 1 + S（左端のSのルール2による）

→ 1 + 1 + a（左端のSのルール3により）、

要約すると

ルール1

ルール2

ルール1

ルール2

ルール3。

最も右端の導出は次のようになります。

S

→ S + S（右端のSのルール1による）

→ S + S + S（右端のSのルール1による）

→ S + S + a（右端のSのルール3による）

→ S + 1 + a（右端のSのルール2による）

→ 1 + 1 + a（右端のSのルール2により）、

要約すると

ルール1

ルール1

ルール3

ルール2

ルール2。

ほとんどのパーサーでは、ルールが適用されるたびに実行されるすべての文法ルールに対してコード片を与えることによって入力の変換が定義されるため、左端導出と右端導出の区別は重要です。したがって、パーサーが左端導出を決定するか右端導出を決定するかを知ることは重要です。これは、コード片が実行される順序を決定するためです。例として、LL パーサーとLR パーサーを参照してください。

導出は、ある意味では、導出された文字列に階層構造を課します。たとえば、文字列「1 + 1 + a」が上記の左端の導出に従って導出された場合は、文字列の構造は次のようになります。

{{1} _S + {{1} _S + { a } _S } _S } _S

ここで、{...} _{S は}Sに属すると認識される部分文字列を示します。この階層はツリーとして見ることもできます。

このツリーは、抽象構文木とは対照的に、文字列の構文解析木または「具体的な構文木」と呼ばれます。この場合、提示された左端と右端の導出は同じ構文解析木を定義しますが、同じ文字列の別の右端の導出があります。

S

→ S + S（右端のSのルール1による）

→ S + a（右端のSのルール3による）

→ S + S + a（右端のSのルール1による）

→ S + 1 + a（右端のSのルール2による）

→ 1 + 1 + a（右端のSのルール2により）、

異なる構造を持つ文字列を定義する

{{{1} _S + {1} _S } _S + { a } _S } _S

異なる解析ツリー:

ただし、両方の構文解析ツリーは、左端と右端の両方の導出によって取得できることに注意してください。たとえば、最後のツリーは、次のように左端の導出で取得できます。

S

→ S + S（左端のSのルール1による）

→ S + S + S（左端のSのルール1による）

→ 1 + S + S（左端のSのルール2による）

→ 1 + 1 + S（左端のSのルール2による）

→ 1 + 1 + a（左端のSのルール3により）、

文法の言語の文字列に複数の構文解析ツリーがある場合、その文法はあいまいな文法と呼ばれます。このような文法は、パーサーがどの文法規則を適用する必要があるかを常に決定できるとは限らないため、通常、解析が困難です。通常、あいまいさは言語ではなく文法の特徴であり、同じ文脈自由言語を生成するあいまいでない文法が見つかります。ただし、あいまいな文法でしか生成できない言語もあり、そのような言語は本質的にあいまいな言語と呼ばれます。

ε生成を持たないすべての文脈自由文法には、同等のチョムスキー標準形の文法とグライバッハ標準形の文法があります。ここで「同等」とは、2 つの文法が同じ言語を生成することを意味します。

チョムスキー正規形文法における生成規則の特に単純な形式は、理論的および実用的な意味合いを持っています。たとえば、文脈自由文法が与えられた場合、チョムスキー正規形を使用して、与えられた文字列がその文法によって表される言語であるかどうかを判断する多項式時間アルゴリズムを構築できます ( CYK アルゴリズム)。

文脈自由言語はさまざまな演算に対して閉じています。つまり、言語KとLが文脈自由であれば、次の演算の結果も文脈自由になります。

• 和集合 K ∪ L ;連結 K ∘ L ;クリーネスター L ^{* [11]}
• 置換（特に準同型）^[12]
• 逆準同型^[13]
• 正規言語との交差^[14]

これらは一般交差（したがって補集合）と集合差の下では閉じていない。 ^[15]

以下は文脈自由文法に関するいくつかの決定可能な問題です。

与えられた単語が文脈自由文法によって与えられた言語に属しているかどうかを確認する解析問題は、汎用解析アルゴリズムの 1 つを使用して決定可能です。

• CYKアルゴリズム（チョムスキー標準形の文法用）
• アーリーパーサー
• GLRパーサー
• LLパーサー（LL( k )文法の適切なサブクラスのみ）

チョムスキー正規形文法の文脈自由構文解析は^、ブール行列乗算に還元可能であることがレスリー・G・ヴァリアントによって示され、その計算量の上限であるO ( n2.3728639 )を継承した。^{[16] [17] [b]}逆に、リリアン・リーは、 O ( n3 ^{−ε )}のブール行列乗算がO ( n3−3ε )のCFG構文解析に還元可能であることを示しており、後者のある種の下限を確立している。^[18]

非終端記号は、終端記号の文字列に導出がある場合、生産的または生成的であると呼ばれます。開始記号から非終端記号と終端記号の文字列に導出がある場合、到達可能であると呼ばれます。到達不可能または非生産的である場合、役に立たないと呼ばれます。導出がある場合、ヌル可能と呼ばれます。規則はε 生成と呼ばれます。導出はサイクルと呼ばれます。 ${\displaystyle X}$${\displaystyle X{\stackrel {*}{\Rightarrow }}w}$${\displaystyle w}$${\displaystyle X}$${\displaystyle S{\stackrel {*}{\Rightarrow }}\alpha X\beta }$${\displaystyle \alpha ,\beta }$${\displaystyle X}$${\displaystyle X}$${\displaystyle X{\stackrel {*}{\Rightarrow }}\varepsilon }$${\displaystyle X\rightarrow \varepsilon }$${\displaystyle X{\stackrel {+}{\Rightarrow }}X}$

アルゴリズムは、生成された言語を変更することなく、与えられた文法から次のものを除去することが知られている。

• 非生産的な記号、^{[19] [c]}
• 到達不可能なシンボル、^{[21] [22]}
• ε-生成は、1つの例外を除いて^{[d] [23]}と
• サイクル。^[e]

特に、役に立たない非終端記号を含む選択肢は、規則の右側から削除することができます。このような規則と選択肢は、役に立たないと呼ばれます。^[24]

示されている例の文法では、非終端記号D は到達不能であり、E は非生産的であり、C → C は循環を引き起こします。したがって、最後の 3 つの規則を省略しても、文法によって生成される言語は変更されません。また、Sの規則の右側から選択肢 "| Cc | Ee " を省略しても、文法によって生成される言語は変更されません。

文脈自由文法は、無駄な記号もε生成も循環も持たない場合に適切であると言われる。 ^{[25]上記のアルゴリズムを組み合わせると、εを生成しないすべての文脈自由文法は、}弱等価な適切な文法 に変換できる。

与えられた文法が正規文法であるかどうかは決定可能である^[f]。また、与えられたk≥0に対してLL ( k )文法であるかどうかも決定可能である^{[26] ：233} kが与えられていない場合、後者の問題は決定不可能である^{[26] ：252}

文脈自由文法が与えられた場合、その言語が正規言語であるかどうかは決定できず、^[27]与えられたkに対してLL( k )言語であるかどうかも決定できない。^{[26] : 254}

与えられた文脈自由文法の言語が空であるかどうか、また有限であるかどうかを判断するアルゴリズムが存在する。^[28]

より広いクラスの文法では決定不可能ないくつかの質問は、文脈自由文法では決定可能になります。たとえば、空の問題(文法が終端文字列を生成するかどうか) は、文脈依存文法では決定不可能ですが、文脈自由文法では決定可能です。

しかし、多くの問題は文脈自由文法でも決定不可能であり、その中でも最も顕著なものを以下で扱います。

CFGが与えられた場合、そのルールで使用される終端記号のアルファベット上のすべての文字列の言語を生成するか？^{[29] [30]}

チューリングマシンが特定の入力を受け入れるかどうかを決定するというよく知られた決定不可能な問題(停止問題) から、この問題への還元を示すことができます。この還元では、計算履歴の概念、つまりチューリングマシンの計算全体を記述する文字列を使用します。特定の入力に対する特定のチューリングマシンの計算履歴を受け入れないすべての文字列を生成する CFG を構築できます。これにより、マシンがその入力を受け入れない場合にのみ、すべての文字列が受け入れられます。

2つのCFGが与えられた場合、それらは同じ言語を生成するでしょうか？^{[30] [31]}

この問題の決定不能性は、前の問題の直接的な結果です。つまり、CFG がすべての文字列の言語を定義する単純な CFG と同等であるかどうかを判断することさえ不可能です。

2つのCFGが与えられた場合、最初のCFGは2番目のCFGが生成できるすべての文字列を生成できますか？^{[30] [31]}

この問題が決定可能であれば、言語の等価性も決定できます。つまり、 がのサブセットでありが のサブセットである場合、2 つの CFGと は同じ言語を生成します。 ${\displaystyle G_{1}}$${\displaystyle G_{2}}$${\displaystyle L(G_{1})}$${\displaystyle L(G_{2})}$${\displaystyle L(G_{2})}$${\displaystyle L(G_{1})}$

グライバッハの定理を用いると、次の 2 つの問題は決定不可能であることが示されます。

• 文脈依存文法が与えられた場合、それは文脈自由言語を記述するのでしょうか?
• 文脈自由文法が与えられた場合、それは正規言語を記述することになるだろうか？^{[30] [31]}

CFG が与えられた場合、それは曖昧ですか?

この問題の決定不能性は、曖昧さを決定するアルゴリズムが存在すれば、決定不能であることが知られている郵便対応問題も決定できるという事実から導かれる。 ^{[32]これは}オグデンの補題によって証明できる。^[33]

2 つの CFG がある場合、両方の文法から導出可能な文字列はありますか?

この問題が決定可能であれば、決定不可能なポスト対応問題（PCP）も決定できる。あるアルファベット上の文字列が与えられたとき、文法が以下の規則で構成される とする。${\displaystyle \alpha _{1},\ldots ,\alpha _{N},\beta _{1},\ldots ,\beta _{N}}$${\displaystyle \{a_{1},\ldots ,a_{k}\}}$${\displaystyle G_{1}}$

${\displaystyle S\to \alpha _{1}S\beta _{1}^{rev}|\cdots |\alpha _{N}S\beta _{N}^{rev}|b}$;

ここで は逆の文字列を表し、には現れません。そして文法⁠ ⁠が規則から構成されるものと します。${\displaystyle \beta _{i}^{rev}}$${\displaystyle \beta _{i}}$${\displaystyle b}$${\displaystyle a_{i}}$${\displaystyle G_{2}}$

${\displaystyle T\to a_{1}Ta_{1}^{rev}|\cdots |a_{k}Ta_{k}^{rev}|b}$;

次に、 ⁠ ⁠と⁠ ⁠ が導出可能な文字列を共有する場合のみ、によって与えられた PCP インスタンスに解が存在します。文字列の左側 ( の前) は PCP インスタンスの解の上部を表し、右側は逆に下部になります。 ${\displaystyle \alpha _{1},\ldots ,\alpha _{N},\beta _{1},\ldots ,\beta _{N}}$${\displaystyle L(G_{1})}$${\displaystyle L(G_{2})}$${\displaystyle b}$

文脈自由文法の形式主義を拡張する明白な方法は、非終端記号に引数を持たせ、その値をルール内で受け渡すことです。これにより、一致や参照などの自然言語機能や、識別子の正しい使用法や定義などのプログラミング言語の類似物を自然な方法で表現できます。たとえば、英語の文章では主語と動詞の数が一致する必要があることを簡単に表現できます。コンピューターサイエンスでは、このアプローチの例として、接辞文法、属性文法、インデックス文法、Van Wijngaarden 2レベル文法などがあります。言語学にも同様の拡張が存在します。

拡張文脈自由文法（または正規右部文法）は、生成規則の右側に文法の終端記号と非終端記号に対する正規表現を記述できる文法である。拡張文脈自由文法は文脈自由言語を正確に記述する。 ^[34]

もう 1 つの拡張は、ルールの左側に追加の終端記号を表示して、その適用を制限することです。これにより、文脈依存文法の形式主義が生成されます。

文脈自由文法には重要なサブクラスがいくつかあります。

• LR( k )文法（決定性文脈自由文法とも呼ばれる）は、決定性プッシュダウンオートマトン（PDA）による構文解析（文字列認識）を可能にしますが、決定性文脈自由言語しか記述できません。
• シンプル LR、先読み LR文法は、解析をさらに簡素化できるサブクラスです。SLR と LALR は、ほとんどの場合、LR と同じ PDA を使用して認識されますが、より単純なテーブルが使用されます。
• LL( k ) 文法と LL( * )文法では、上記のように左端導出を直接構築することによって構文解析が可能になり、記述できる言語はさらに少なくなります。
• 単純文法はLL(1)文法のサブクラスであり、単純文法の言語の等価性は決定可能であるが、言語の包含は決定できないという理論的性質が興味深い。
• 括弧付き文法には、終端記号がルール内で常に一致する左括弧と右括弧のペアに分割されるという特性があります。
• 線形文法には、右側に複数の非終端記号を持つ規則はありません。
• 正規文法は線形文法のサブクラスであり、正規言語を記述します。つまり、有限オートマトンと正規表現に対応します。

LR 構文解析は LL 構文解析を拡張して、より広範囲の文法をサポートします。一方、一般化 LR 構文解析はLR 構文解析を拡張して、任意の文脈自由文法をサポートします。LL 文法と LR 文法では、基本的にそれぞれ LL 構文解析と LR 構文解析を実行しますが、非決定性文法では、期待どおりの効率性を発揮します。GLR 構文解析は 1980 年代に開発されましたが、現在に至るまで、多くの新しい言語定義とパーサー ジェネレーターはLL、LALR、または LR 構文解析に基づいています。

チョムスキーは当初、変換規則を追加することで文脈自由文法の限界を克服することを望んでいた。^[4]

このような規則は、英語の受動化など、伝統的な言語学におけるもう 1 つの標準的な手段です。生成文法の多くは、句構造文法と変換規則の記述メカニズムを洗練して、自然言語が実際に許可している種類のことを正確に表現できるようにする方法を見つけることに費やされてきました。任意の変換を許可することは、その目的を達成しません。変換は非常に強力であり、重要な制限が追加されない限りチューリング完全です(たとえば、コンテキストフリーの方法で記号を導入して書き換える変換はありません)。

それ以来、チョムスキーの自然言語の非文脈自由性に関する一般的な立場は維持されているが^[35]、文脈自由文法の弱い生成能力の点での不十分さに関する彼の具体的な例は後に反証された。^[36] ジェラルド・ガズダーとジェフリー・プルムは、自然言語には文脈自由でない構文がいくつかあるにもかかわらず（スイスドイツ語のクロスシリアル依存関係^[35]やバンバラ語の重複^[37]など）、自然言語の形式の大部分は確かに文脈自由であると主張している。^[36]

• 構文解析式の文法
• 確率的文脈自由文法
• 文脈自由文法生成アルゴリズム
• 文脈自由言語のポンピング補題

• ホップクロフト、ジョン E.、ウルマン、ジェフリー D. (1979)。オートマトン理論、言語、計算入門(第 1 版)。アディソン ウェスレー。ISBN 0-201-02988-X。 （印刷障害のある利用者も閲覧可能）第4章：文脈自由文法、77～106ページ、第6章：文脈自由言語の特性、125～137ページ。
• ホップクロフト、ジョン E. ;モトワニ、ラジーブ;ウルマン、ジェフリー D. (2006) [1979].オートマトン理論、言語、計算入門(第 3 版). Addison-Wesley. ISBN 0-321-45536-3。
• シプサー、マイケル(1997)。計算理論入門(第 1 版)。PWS 出版。ISBN 978-0-534-94728-6。(印刷障害のある利用者もアクセス可能) 第 2 章: 文脈自由文法、pp. 91–122; セクション 4.1.2: 文脈自由言語に関する決定可能問題、pp. 156–159; セクション 5.1.1: 計算履歴による縮約: pp. 176–183。
• J. Berstel、L. Boasson (1990)。Jan van Leeuwen (編)。文脈自由言語。理論計算機科学ハンドブック。第 B 巻。エルゼビア。pp. 59–102。

• コンピュータ プログラマーにとっては、Stack Exchange の回答が役に立つかもしれません。
• CFG Developer は、2014 年にスタンフォード大学の Christopher Wong によって作成され、2015 年に Kevin Gibbons によって修正されました。