文脈自由言語

$L$ を正規言語とすると、正規言語 の記事の定義により、右線形文法 $G=(V,\Sigma,R,S)$（各規則が $A\to wB$ または $A\to w$、$w\in\Sigma^{*}$、$B\in V$ の形）で $L=L(G)$ となるものがある。右線形文法の規則は左辺が一つの変数記号で右辺が $(V\cup\Sigma)^{*}$ の元であるから、$G$ は文脈自由文法の条件を満たし、導出と生成言語の定義も同じである。よって $L=L(G)$ は文脈自由言語である。逆が成り立たないことは ex-context-free-language-anbn による。

（導出から構文木へ）導出の長さ $n$ に関する帰納法。$n=0$ なら $\gamma=A$ であり、根だけの木がよい。$n\ge1$ なら導出は $A\Rightarrow^{*}\gamma'\Rightarrow\gamma$ と書け、最後の一歩は $\gamma'=\gamma_1B\gamma_2$ の $B$ を規則 $B\to\beta$ で置き換えて $\gamma=\gamma_1\beta\gamma_2$ を得るものである。帰納法の仮定により生成文字列 $\gamma'$ の構文木があり、その葉のうち置き換えた $B$ の出現に対応する葉に、$\beta$ の記号をラベルとする子（$\beta=\varepsilon$ なら $\varepsilon$ の子一つ）を付ければ、生成文字列 $\gamma$ の構文木になる。
（構文木から導出へ）構文木の頂点数に関する帰納法。根だけなら $\gamma=A$ で $A\Rightarrow^{0}A$。根が子 $X_1,\ldots,X_k$ を持つ（$A\to X_1\cdots X_k$ が規則）なら、各 $X_i$ を根とする部分木の生成文字列を $\gamma_i$ とすると $\gamma=\gamma_1\cdots\gamma_k$ であり、帰納法の仮定により $X_i\Rightarrow^{*}\gamma_i$（$X_i$ が終端記号または $\varepsilon$ なら $\gamma_i=X_i$ で $0$ 歩）。導出は前後に文字列を付けても実行できる（Backus–Naur記法 の記事の命題の証明の冒頭の注意）ので、$A\Rightarrow X_1\cdots X_k\Rightarrow^{*}\gamma_1X_2\cdots X_k\Rightarrow^{*}\cdots\Rightarrow^{*}\gamma_1\cdots\gamma_k=\gamma$ が得られる。規則 $A\to\varepsilon$ の場合は $k=0$ とみなせばよい。

$L=L(G)$、$G=(V,\Sigma,R,S)$ とし、
$$b:=\max\{\,2,\ \text{規則の右辺の長さの最大値}\,\}$$
とおく（$b\ge2$ であり、どの規則の右辺の長さも $b$ 以下である）。変数記号の個数を $k:=|V|$ とし、$p:=b^{k+1}$ とおく。
構文木の各頂点の子は高々 $b$ 個なので、根からの最長経路の頂点数（高さ $+1$）が $h$ の構文木の葉は高々 $b^{h-1}$ 個であり、したがって生成文字列の長さも高々 $b^{h-1}$ である（$\varepsilon$ の葉は長さに寄与しない）。
$|w|\ge p=b^{k+1}$ なる $w\in L$ をとる。lem-context-free-language-tree-derivation により $S$ を根とし生成文字列 $w$ の完全な構文木が存在する。その中で頂点数が最小のものを $T$ とし、$T$ の最長経路の頂点数を $h$ とする。上の評価により $|w|\le b^{h-1}$ であり、$b\ge2$ より $b^{k}< b^{k+1}=p\le|w|$ であるから、$h-1\ge k+1$、すなわち $T$ の最長経路の頂点数 $h$ は $k+2$ 以上である。その経路の末端は葉（終端記号または $\varepsilon$）なので、経路上には少なくとも $k+1$ 個の変数記号のラベルを持つ頂点がある。経路を葉から根に向かってたどり、変数記号のラベルを持つ頂点を下から $k+1$ 個とると、変数記号は $k$ 種類しかないので、鳩の巣原理により同じ変数記号 $A$ のラベルを持つ二つの頂点 $\nu_1$（上）と $\nu_2$（下）がある。
$\nu_1$ を根とする部分木の生成文字列を $vxy$、$\nu_2$ を根とする部分木の生成文字列を $x$ とし（$\nu_2$ は $\nu_1$ の子孫なので $x$ は $vxy$ の部分文字列であり、その左側を $v$、右側を $y$ とする）、$w$ の残りを $u,z$ として $w=uvxyz$ と書く。lem-context-free-language-tree-derivation により
$$S\Rightarrow^{*}uAz,\qquad A\Rightarrow^{*}vAy,\qquad A\Rightarrow^{*}x$$
である。
条件 3：中央の導出 $A\Rightarrow^{*}vAy$ を $m$ 回繰り返してから $A\Rightarrow^{*}x$ を使えば、$S\Rightarrow^{*}uAz\Rightarrow^{*}uv^{m}Ay^{m}z\Rightarrow^{*}uv^{m}xy^{m}z$ となり、$uv^{m}xy^{m}z\in L$ である（$m=0$ のときは $\nu_1$ の部分木を $\nu_2$ の部分木で置き換えた木に対応する）。
条件 1：$v=y=\varepsilon$ と仮定すると、$\nu_1$ の部分木を $\nu_2$ の部分木で置き換えた木は、生成文字列が $uxz=w$ のままで頂点数が真に少ない $S$ を根とする完全な構文木になり、$T$ の最小性に反する。よって $|vy|\ge1$。
条件 2：$\nu_1$ は最長経路上の、下から数えて $k+1$ 個目までの変数記号の頂点であるから、選んだ経路のうち $\nu_1$ から葉までの部分の頂点数は高々 $k+2$ である（変数記号の頂点が高々 $k+1$ 個、その下に葉が一つ）。選んだ経路は $T$ の根からの最長経路なので、その $\nu_1$ 以下の部分は $\nu_1$ を根とする部分木の中の最長経路でもある（より長い経路があれば、根から $\nu_1$ までの部分と継いで $T$ のより長い経路が得られる）。よって $\nu_1$ を根とする部分木の生成文字列の長さは $|vxy|\le b^{k+1}=p$ である。

$L$ が文脈自由であると仮定し、prop-context-free-language-pumping の反復定数 $p$ をとる。$w=a^{p}b^{p}c^{p}\in L$ は $|w|\ge p$ なので、$w=uvxyz$、$|vy|\ge1$、$|vxy|\le p$、すべての $m$ について $uv^{m}xy^{m}z\in L$ となる分解がある。$|vxy|\le p$ より、$vxy$ は $w$ の中の連続した $p$ 記号以下の部分なので、$a$ と $c$ の両方を含むことはできない（$a$ の最後と $c$ の最初の間には $p$ 個の $b$ がある）。$m=2$ とすると $uv^{2}xy^{2}z$ は、$vy$ に含まれる記号の個数だけが増え（$|vy|\ge1$ なので少なくとも一種類は真に増える）、$vxy$ に含まれない記号の個数は $p$ のままである。$vxy$ は $a$ か $c$ の少なくとも一方を含まないので、$uv^{2}xy^{2}z$ では $a,b,c$ の個数がすべて等しいという条件が崩れ、$uv^{2}xy^{2}z\notin L$ となる。これは矛盾である。

$L_i=L(G_i)$、$G_i=(V_i,\Sigma,R_i,S_i)$ とし、変数記号の名前を付け替えて $V_1\cap V_2=\emptyset$ とする。新しい変数記号 $S\notin V_1\cup V_2$ をとる。
和集合：$G_\cup:=(V_1\cup V_2\cup\{S\},\Sigma,R_1\cup R_2\cup\{S\to S_1,S\to S_2\},S)$。$S$ からの導出は最初の一歩で $S_1$ か $S_2$ を選び、以後 $V_1$ の規則だけ（または $V_2$ の規則だけ）を使うので、$L(G_\cup)=L_1\cup L_2$ である。
連接：$G_\cdot:=(V_1\cup V_2\cup\{S\},\Sigma,R_1\cup R_2\cup\{S\to S_1S_2\},S)$。$S\Rightarrow S_1S_2\Rightarrow^{*}w$ なる $w\in\Sigma^{*}$ に対し、Backus–Naur記法 の記事の補題（導出の分解補題）により $w=w_1w_2$、$S_1\Rightarrow^{*}w_1$、$S_2\Rightarrow^{*}w_2$ と分解でき、$S_i$ からの導出では $V_i$ の規則しか使えないので $w_i\in L_i$ である。逆に $w_1\in L_1$、$w_2\in L_2$ なら $S\Rightarrow S_1S_2\Rightarrow^{*}w_1S_2\Rightarrow^{*}w_1w_2$。よって $L(G_\cdot)=L_1L_2$。
Kleene 閉包：$L=L(G)$、$G=(V,\Sigma,R,S_0)$ とし、$G_{*}:=(V\cup\{S\},\Sigma,R\cup\{S\to S_0S,\ S\to\varepsilon\},S)$。$w\in L(G_{*})$ とし、lem-context-free-language-tree-derivation により $S$ を根とする完全な構文木をとる。$S$ の規則は $S\to S_0S$ と $S\to\varepsilon$ だけなので、この木は根から右端の子をたどる経路上に $S$ が $n+1$ 個並び、最後の $S$ の子が $\varepsilon$、途中の各 $S$ の左の子が $S_0$ という形をしており、生成文字列は $n$ 個の $S_0$ を根とする部分木の生成文字列 $w_1,\ldots,w_n$ の連接である。再び補題により $S_0\Rightarrow_G^{*}w_i$、すなわち $w_i\in L$ であるから $w\in L^{n}\subset L^{*}$。逆に $w_1,\ldots,w_n\in L$ なら $S\Rightarrow^{*}S_0^{n}S\Rightarrow S_0^{n}\Rightarrow^{*}w_1\cdots w_n$ である。よって $L(G_{*})=L^{*}$。
鏡像：$G^{\mathrm{R}}:=(V,\Sigma,\{A\to\alpha^{\mathrm{R}}\mid A\to\alpha\in R\},S_0)$ とおくと、これは文脈自由文法であり、正規言語 の記事の命題（左線形文法との同値）の証明中の補題（規則の右辺を鏡像にした文法は鏡像言語を生成する）により $L(G^{\mathrm{R}})=L(G)^{\mathrm{R}}=L^{\mathrm{R}}$ である。

$\Sigma=\{a,b,c\}$ とし、$L_1:=\{\,a^{n}b^{n}c^{m}\mid n,m\in\mathbb{N}\,\}$、$L_2:=\{\,a^{m}b^{n}c^{n}\mid n,m\in\mathbb{N}\,\}$ とおく。$L_1$ は文法 $S\to AC$、$A\to aAb\mid\varepsilon$、$C\to cC\mid\varepsilon$ で生成される。実際 $A$ が生成するのは $\{a^{n}b^{n}\}$（ex-context-free-language-anbn と同じ）、$C$ が生成するのは $\{c^{m}\}$ であり、分解補題により $S$ が生成するのはそれらの連接である。$L_2$ も同様に $S\to AC$、$A\to aA\mid\varepsilon$、$C\to bCc\mid\varepsilon$ で生成される。ところが $L_1\cap L_2=\{\,a^{n}b^{n}c^{n}\mid n\in\mathbb{N}\,\}$ であり、これは prop-context-free-language-anbncn により文脈自由でない。
補集合について、文脈自由言語のクラスが補集合で閉じていると仮定すると、prop-context-free-language-closure の和集合の閉包性と De Morganの法則 $L_1\cap L_2=\Sigma^{*}\setminus\bigl((\Sigma^{*}\setminus L_1)\cup(\Sigma^{*}\setminus L_2)\bigr)$ により共通部分でも閉じることになり、前半に矛盾する。よって補集合が文脈自由でない文脈自由言語が存在する。

変数記号 $A$ が $A\Rightarrow^{*}\varepsilon$ を満たすとき $A$ を消去可能という。消去可能な変数記号の集合 $N$ は、次の規則で閉じた最小の集合として計算できる：$A\to\varepsilon\in R$ なら $A\in N$；$A\to B_1\cdots B_k\in R$ で $B_1,\ldots,B_k\in N$ なら $A\in N$。実際、この規則で得られる変数記号が消去可能なことは構成に関する帰納法で明らかであり、逆に $A\Rightarrow^{*}\varepsilon$ なら、導出の最初の一歩 $A\Rightarrow X_1\cdots X_k$ の右辺は変数記号だけからなり（終端記号は消えない）、分解補題により各 $X_i\Rightarrow^{*}\varepsilon$ がより短い導出で成り立つので、導出の長さに関する帰納法により $A\in N$ である。
規則の集合 $R_1$ を、$R$ の各規則 $A\to\alpha$ に対し、$\alpha$ に現れる $N$ の元の出現のうち任意個（$0$ 個でもよい）を削除して得られる文字列 $\beta$ で $\beta\ne\varepsilon$ となるものすべてについて $A\to\beta$ を集めたものとする。$R_1$ は $\varepsilon$ 規則を含まない。主張：任意の変数記号 $A$ と空でない $w\in\Sigma^{*}$ について、$A\Rightarrow_{R_1}^{*}w$ と $A\Rightarrow_{R}^{*}w$ は同値である。
（$R_1$ から $R$ へ）$R_1$ の規則 $A\to\beta$ は、$R$ の規則 $A\to\alpha$ から消去可能な変数記号を削除したものなので、$R$ において $A\Rightarrow\alpha\Rightarrow^{*}\beta$ が成り立つ（削除した各変数記号から $\varepsilon$ を導出する）。よって $R_1$ の導出の各一歩を $R$ の導出で置き換えられる。
（$R$ から $R_1$ へ）$A\Rightarrow_R^{*}w$（$w\ne\varepsilon$）の長さ $n\ge1$ に関する帰納法。最初の一歩を $A\Rightarrow X_1\cdots X_k$ とすると、分解補題により $w=w_1\cdots w_k$、$X_i\Rightarrow_R^{*}w_i$ であり、各導出の長さは $n$ 未満である。$w_i=\varepsilon$ となる $i$ については $X_i$ は変数記号で $X_i\in N$ である（終端記号なら $w_i=X_i\ne\varepsilon$）。それらの出現を $X_1\cdots X_k$ から削除した文字列を $\beta$ とすると、$w\ne\varepsilon$ より $\beta\ne\varepsilon$ なので $A\to\beta\in R_1$ である。残った各 $X_i$ については $w_i\ne\varepsilon$ なので帰納法の仮定により $X_i\Rightarrow_{R_1}^{*}w_i$ であり、これらをつなげば $A\Rightarrow_{R_1}\beta\Rightarrow_{R_1}^{*}w$ を得る。
最後に、新しい変数記号 $S'\notin V$ をとり、$R':=R_1\cup\{S'\to S\}$ とし、$\varepsilon\in L(G)$（すなわち $S\in N$）のときに限り規則 $S'\to\varepsilon$ を $R'$ に加えて、$G':=(V\cup\{S'\},\Sigma,R',S')$ とおく。$R_1$ の規則の右辺は $R$ の規則の右辺から記号を削除したものなので $S'$ を含まず、$S'\to S$ と $S'\to\varepsilon$ の右辺も $S'$ を含まないから、$S'$ はどの規則の右辺にも現れない。また $R'$ の $\varepsilon$ 規則は高々 $S'\to\varepsilon$ だけであり、それがあるのは $\varepsilon\in L(G)$ のときに限る。$S'$ からの導出は最初の一歩で $S'\to S$ または $S'\to\varepsilon$ を使い、以後 $S'$ は現れないので、空でない $w\in\Sigma^{*}$ については $w\in L(G')$ と $S\Rightarrow_{R_1}^{*}w$ が同値であり、上の主張によりこれは $S\Rightarrow_R^{*}w$、すなわち $w\in L(G)$ と同値である。$\varepsilon$ については、$R_1$ が $\varepsilon$ 規則を含まないので $S\Rightarrow_{R_1}^{*}\varepsilon$ は起こらず、$\varepsilon\in L(G')$ は $S'\to\varepsilon\in R'$、すなわち $\varepsilon\in L(G)$ と同値である。よって $L(G')=L(G)$ である。