構文解析

要点：最左導出では、左の記号から出る部分の書き換えがすべて終わってから右の記号に進むので、最左導出も構文木も「根の規則と、子ごとの部分」に一通りに分かれる。

1：$S$ はどの規則の右辺にも現れないので、$A\ne S$ から始まる導出に $S$ は現れず、規則 $S\to\varepsilon$ は使われない。残りの規則は文字列を短くしないので、長さは $1$ 以上のままである。
2・3：$A\Rightarrow^{*}w$ の最初の一歩で分ける。規則 $S\to\varepsilon$ なら $w=\varepsilon$ である。規則 $A\to a$ なら $w=a$ である。規則 $A\to BC$ なら、Backus–Naur記法 の補題「導出の分解補題」により $w=yz$、$B\Rightarrow^{*}y$、$C\Rightarrow^{*}z$ と書け、$B,C\ne S$ なので 1 により $y,z\ne\varepsilon$、特に $\lvert w\rvert\ge2$ である。よって $\lvert w\rvert=1$ なら最初の一歩は $A\to w$ であり、$\lvert w\rvert\ge2$ なら最初の一歩は $A\to BC$ の形で 3 の分解がある。$\square$

$x_{ij}:=a_i\cdots a_j$ と書き、$U(i,j):=\{A\mid A\Rightarrow^{*}x_{ij}\}$ とおく。$\ell=j-i$ についての帰納法で $T(i,j)=U(i,j)$ を示す。
$\ell=0$ のとき：lem-parsing-cnf-shape の 2 により、$A\Rightarrow^{*}a_i$ は $A\to a_i\in R$ と同値である（逆向きは一歩の導出）。よって $T(i,i)=U(i,i)$ である。
$\ell\ge1$ のとき：$A\in T(i,j)$ なら、規則 $A\to BC$ と $k$ で $B\in T(i,k)$、$C\in T(k+1,j)$ となるものがある。$k-i$ と $j-(k+1)$ は $\ell$ より小さいので、帰納法の仮定により $B\Rightarrow^{*}x_{ik}$、$C\Rightarrow^{*}x_{k+1,j}$ であり、$A\Rightarrow BC\Rightarrow^{*}x_{ik}C\Rightarrow^{*}x_{ik}x_{k+1,j}=x_{ij}$ となるので $A\in U(i,j)$ である。逆に $A\in U(i,j)$ なら、$\lvert x_{ij}\rvert=\ell+1\ge2$ なので lem-parsing-cnf-shape の 3 により、規則 $A\to BC$ と分解 $x_{ij}=yz$（$y,z\ne\varepsilon$）で $B\Rightarrow^{*}y$、$C\Rightarrow^{*}z$ となるものがある。$y=x_{ik}$、$z=x_{k+1,j}$ となる $k$ は $i\le k< j$ を満たし、帰納法の仮定により $B\in T(i,k)$、$C\in T(k+1,j)$ なので $A\in T(i,j)$ である。
$w\in L(G)$ は $S\Rightarrow^{*}x_{1n}$ のことなので、$S\in U(1,n)=T(1,n)$ と同値である。$\ell$ の小さい順に $T(i,j)$ を作れば、右辺に現れる $T$ はすでに求まっている。$i\le k< j$ を満たす $(i,k,j)$ の組は $\binom{n+1}{3}\le n^{3}$ 個で、各組で規則を高々 $\lvert R\rvert$ 個調べればよい（$\ell=0$ の段の $n\lvert R\rvert$ 回もこの上界に収まる）。$\square$

要点：生成文字列が長さ 2 以上の構文木は、根の規則 $A\to BC$、左の部分木の生成文字列の長さ（分割点 $k$）、2 つの部分木の組で一通りに決まる。

(a) 最左導出のなぞり。 $D$ を最左導出 $\gamma\Rightarrow_{\mathrm{lm}}^{*}u$ とする。$D$ の歩数と $\lvert\gamma\rvert$ の組について辞書式順序の帰納法で、手続きが $(u,\gamma)$ から $D$ の規則を順に展開して受理することを示す。$\gamma=\varepsilon$ なら $u=\varepsilon$ で受理する。$\gamma=a\gamma'$ なら、先頭の $a$ は書き換わらないので $u=au'$ で、$D$ は最左導出 $\gamma'\Rightarrow_{\mathrm{lm}}^{*}u'$ を与え、手続きは照合して $(u',\gamma')$ に進む。$\gamma=A\gamma'$ なら、$D$ の最初の一歩は最左なので $A$ をある規則 $A\to\alpha$ で書き換える。Backus–Naur記法 の補題「導出の分解補題」により $u=yz$、$\alpha\Rightarrow^{*}y$、$\gamma'\Rightarrow^{*}z$ と書け、空語規則がないので $y\ne\varepsilon$ である。$y$ の最初の文字を $a$ とすると $u=au'$ かつ $a\in\mathrm{FIRST}(\alpha)$ なので、手続きは同じ規則で展開して $(u,\alpha\gamma')$ に進み、残りは歩数の少ない最左導出である。
(b) 受理の正しさ。 手続きが受理するなら、歩数についての帰納法で $\gamma\Rightarrow^{*}u$ である。展開は導出の一歩で、照合は先頭の共通の文字を外すだけだからである。
(c) 停止。 照合は高々 $\lvert u\rvert$ 回である。照合と照合のあいだ（と最初の照合の前）の展開を考える。残りの入力の先頭が $a$ のまま展開が $A_1,A_2,\dots$ と続くとき、$A_{t+1}$ は、$A_t$ の規則のうち $a$ を FIRST に含む唯一のもの $A_t\to\alpha_t$ の右辺の先頭の記号である（先頭が終端記号なら、それは $a$ で次は照合になる）。この「次の記号」を $\nu(A)$ と書く。$A_1$ について $a\in\mathrm{FIRST}(A_1)$ なので $A_1\Rightarrow^{*}ax$ となる導出があり、その構文木の根から一番左の葉 $a$ までの道 $A_1=Y_0,Y_1,\dots,Y_m=a$ では、各頂点の規則の右辺は $Y_{s+1}$ で始まり $a$ を FIRST に含むので、$Y_{s+1}=\nu(Y_s)$ である。もし $A_i=A_j$（$i< j$）なら、$\nu$ を繰り返すと $A_i,\dots,A_{j-1}$ を周期的に回り続けて終端記号に達しないが、$Y_0=A_1$ から $\nu$ を繰り返すと $m$ 回で $a$ に達するので矛盾する。よって $A_t$ は相異なり、展開は高々 $\lvert V\rvert$ 回続く。入力を読み終えた後は、一番上が終端記号でも非終端記号でも $1$ 歩で停止する。歩数は合わせて高々 $\lvert u\rvert+\lvert V\rvert\,\lvert u\rvert+1$ である。
(d) まとめ。 $\gamma\Rightarrow^{*}u$ なら、$\gamma=X_1\cdots X_m$ に導出の分解補題を当てて $u=u_1\cdots u_m$、$X_i\Rightarrow^{*}u_i$ と分け、各 $X_i$ の最左導出（prop-parsing-tree-leftmost と 文脈自由言語 の補題「構文木と導出の対応」）を左から順に並べると最左導出 $\gamma\Rightarrow_{\mathrm{lm}}^{*}u$ が得られ、(a) により受理する。逆は (b) である。最左導出は使う規則の列で決まり、(a) により 2 つの最左導出はどちらも決定的な手続きの展開の列に一致するので、等しい。$\gamma=S$ とし prop-parsing-tree-leftmost を使えば、$G$ は曖昧でない。$\square$