文脈自由言語 | 計算理論 | 天游ヶ丘数理学院

1 文法、導出、構文木

終端記号と非終端記号は互いに重ならない有限集合として固定する。

定義 1.1. 文脈自由文法 (context-free grammar)（CFG）は、四項組

G=(V,\Sigma,P,S)

である。 $V$ は有限な非終端記号集合、 $\Sigma$ は有限な終端記号集合であり、 $V\cap\Sigma=\varnothing$ とする。 $S\in V$ は開始記号である。 $P$ は有限な生成規則集合であり、各規則は

A\longrightarrow\gamma \qquad (A\in V,\ \gamma\in(V\cup\Sigma)^*)

の形をもつ。右辺 $\gamma=\varepsilon$ も許す。

規則 $A\to\gamma$ を用いて

\alpha A\beta\Rightarrow_G\alpha\gamma\beta

と書く。 $\Rightarrow_G$ の反射推移閉包を $\Rightarrow_G^*$ と書き、

L(G)=\{w\in\Sigma^*:S\Rightarrow_G^*w\}

を $G$ の生成言語 (generated language) という。ある CFG の生成言語である言語を文脈自由言語 (context-free language) という。

一段導出で置き換える非終端記号より左側に非終端記号がない場合、その導出を左端導出という。左端導出の反射推移閉包を $\Rightarrow_{\mathrm{lm}}^*$ と書く。

導出の途中では、非終端記号がまだ展開されずに残る。この状態も含めて木として表すため、根を任意の非終端記号とし、未展開の葉を許す形で定義する。

定義 1.2. CFG $G=(V,\Sigma,P,S)$ と $A\in V$ に対して、 $A$ -導出木 (A-derivation tree) は、根付き順序木であって、次を満たすものである。

根は $A$ で標識される。
各頂点は $V\cup\Sigma\cup\{\varepsilon\}$ の元で標識される。 $\Sigma$ または $\varepsilon$ で標識された頂点は葉である。
$B\in V$ で標識された頂点が子をもち、どの子も $V\cup\Sigma$ で標識されるならば、子の標識を左から並べた語 $X_1\cdots X_k$ について、 $B\to X_1\cdots X_k$ は $P$ の規則である。
$B\in V$ で標識された頂点の子が、 $\varepsilon$ で標識された一つの葉だけである場合、 $B\to\varepsilon$ は $P$ の規則である。頂点が子をもつのは、条件 (c)または条件 (d)の場合に限る。

$V$ で標識された葉を未展開の葉 (unexpanded leaf) という。葉の標識を左から並べ、 $\varepsilon$ で標識された葉は記号を寄与しないものとして得られる $(V\cup\Sigma)^*$ の元を、その木の成果 (yield)（yield）という。頂点 $v$ に対して、 $v$ を根とする部分木の成果を $\mathrm{yield}(v)$ と書く。

未展開の葉をもたない $A$ -導出木を完成した (completed) $A$ -導出木といい、その成果は $\Sigma^*$ に属する。完成した $S$ -導出木を $G$ の構文木 (parse tree) という。

任意の導出は、生成規則を左端から適用する導出へ並べ替えることができる。この事実を導出木を介して証明する。根を任意の非終端記号とするのは、証明の帰納段で部分木へ帰納法の仮定を適用するためである。

命題 1.3. $G=(V,\Sigma,P,S)$ 、 $A\in V$ および $w\in\Sigma^*$ に対して、次の三条件は同値である。

$A\Rightarrow_G^*w$ 。
$A\Rightarrow_{\mathrm{lm}}^*w$ 。
成果が $w$ である完成した $A$ -導出木が存在する。

とくに $A=S$ の場合、三条件は $w\in L(G)$ と同値である。

証明.(2) $\Rightarrow$ (1)は直ちに従う。

(1) $\Rightarrow$ (3)を示す。導出

A=\alpha_0\Rightarrow_G\alpha_1\Rightarrow_G\cdots\Rightarrow_G\alpha_n=w

を一つ取る。 $i$ に関する帰納法で、成果が $\alpha_i$ である $A$ -導出木 $T_i$ を構成する。 $T_0$ は $A$ で標識された根だけからなる木とする。根は未展開の葉であり、子をもたないため、定義の四条件をすべて満たす。

$T_i$ が得られたとする。一段導出 $\alpha_i=\beta B\gamma\Rightarrow_G\beta\delta\gamma=\alpha_{i+1}$ が規則 $B\to\delta$ によるとする。 $T_i$ の成果は $\alpha_i$ であるから、葉を左から読んだとき $\beta$ の直後に来る葉は $B$ で標識され、未展開である。この葉へ、 $\delta$ の記号を左から順に子として付ける。 $\delta=\varepsilon$ の場合には $\varepsilon$ で標識された子を一つ付ける。得られる木 $T_{i+1}$ は定義の四条件を満たす $A$ -導出木であり、その成果は $\beta\delta\gamma=\alpha_{i+1}$ である。

$T_n$ の成果は $w\in\Sigma^*$ であるから、 $T_n$ は未展開の葉をもたない。よって $T_n$ は完成した $A$ -導出木である。

(3) $\Rightarrow$ (2)を示す。完成した $A$ -導出木の内部頂点数に関する帰納法を用いる。

内部頂点が根だけである場合、根の子はすべて葉であり、 $\Sigma$ または $\varepsilon$ で標識される。定義の定義 1.2 条件 (c)または定義 1.2 条件 (d)により、根に対応する規則を一度適用すれば成果 $w$ を得る。

一般の場合、根の子を左から $X_1,\ldots,X_k$ とする。子が $\varepsilon$ で標識された一つの葉だけである場合は上の基底に含まれるため、どの子も $V\cup\Sigma$ で標識されるとしてよい。まず規則

A\to X_1\cdots X_k

を適用する。 $X_j\in V$ である子 $u_j$ について、 $u_j$ を根とする部分木は完成した $X_j$ -導出木であり、その内部頂点数は元の木より真に少ない。帰納法の仮定により、 $\mathrm{yield}(u_j)=w_j$ に対して $X_j\Rightarrow_{\mathrm{lm}}^*w_j$ が成り立つ。この左端導出を、 $j$ の小さい順に適用する。 $X_j\in\Sigma$ である子は、その終端記号をそのまま寄与する。

左側の子をすべて処理し終えた時点では、その左側はすべて終端記号であるから、次の部分木に対する左端導出は木全体でも左端導出である。最後の子まで続けると、木の成果 $w$ を得る。

最後に、 $A=S$ の場合を考える。定義 1.1により $w\in L(G)$ は $S\Rightarrow_G^*w$ と同値であるから、三条件はいずれも $w\in L(G)$ と同値である。▨

例 1.4 (a の並びの後に同数の b が続く言語). 開始記号を $S$ とし、生成規則を

S\to aSb\mid\varepsilon

とする。この文法の生成言語は

\{a^n b^n:n\ge 0\}

である。

実際、 $S\to aSb$ を $n$ 回適用してから $S\to\varepsilon$ を適用すれば $a^n b^n$ を得る。

逆向きには、文形式に関する次の不変量を導出の長さに関する帰納法で示す。 $S$ から到達することができる文形式は、 $a^kSb^k$ または $a^kb^k$ （ $k\ge 0$ ）の形に限る。実際、初期の文形式は $a^0Sb^0$ である。 $a^kSb^k$ に $S\to aSb$ を適用すると $a^{k+1}Sb^{k+1}$ を得て、 $S\to\varepsilon$ を適用すると $a^kb^k$ を得る。 $a^kb^k$ には非終端記号がないため、これ以上の一段導出は存在しない。個数の一致だけでは $abab$ のような語を排除することができないが、この不変量は語の形まで定めている。終端語である文形式は $a^kb^k$ の形に限るため、生成言語は $\{a^nb^n:n\ge 0\}$ である。

2 Pushdown automaton と受理方式

スタックの左端を上端とする。したがって、スタック語 $X\beta$ では $X$ が上端記号である。

定義 2.1. 非決定性 pushdown automaton (nondeterministic pushdown automaton)（PDA）は、七項組

M=(Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)

である。 $Q$ は有限状態集合、 $\Sigma$ は有限入力アルファベット、 $\Gamma$ は有限スタックアルファベット、 $q_0\in Q$ は初期状態、 $Z_0\in\Gamma$ は初期スタック記号、 $F\subseteq Q$ は受理状態集合である。遷移関数は

\delta:Q\times(\Sigma\cup\{\varepsilon\})\times\Gamma \longrightarrow\mathcal{P}_{\mathrm{fin}}(Q\times\Gamma^*)

である。

配置 (configuration) は $(q,w,\alpha)\in Q\times\Sigma^*\times\Gamma^*$ である。 $(p,\gamma)\in\delta(q,a,X)$ ならば

(q,aw,X\beta)\vdash_M(p,w,\gamma\beta)

とし、 $(p,\gamma)\in\delta(q,\varepsilon,X)$ ならば

(q,w,X\beta)\vdash_M(p,w,\gamma\beta)

とする。第一の遷移は入力 $a$ を一文字消費し、第二の遷移は入力を消費しない。いずれも上端記号 $X$ を語 $\gamma$ に置き換える。

PDA には二つの標準的な受理方式がある。

定義 2.2. PDA $M=(Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)$ が語 $w$ を終状態で受理する (accept by final state) とは、ある $f\in F$ と $\alpha\in\Gamma^*$ が存在して

(q_0,w,Z_0)\vdash_M^*(f,\varepsilon,\alpha)

となることをいう。

受理状態集合を用いない PDA が語 $w$ を空スタックで受理する (accept by empty stack) とは、ある $q\in Q$ が存在して

(q_0,w,Z_0)\vdash_M^*(q,\varepsilon,\varepsilon)

となることをいう。

どちらの定義でも、入力全体を消費しなければ受理にならない。空語遷移だけで受理状態または空スタックへ到達した場合には、空語を受理する。

定理 2.3. 終状態で受理する PDA と空スタックで受理する PDA は、同じ言語のクラスを受理する。

証明. 最初に、終状態で受理する

M=(Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)

を空スタック受理へ変換する。 $Q$ に属さない新しい状態 $s,d$ と、 $\Gamma$ に属さない新しい底記号 $\bot$ をとる。新しい PDA は底記号 $\bot$ だけを初期スタックとし、

(s,w,\bot)\vdash(q_0,w,Z_0\bot)

という空語遷移をもつ。 $M$ の遷移はすべてそのまま複製する。さらに、各 $f\in F$ と $X\in\Gamma\cup\{\bot\}$ に対して

(f,w,X\beta)\vdash(d,w,X\beta)

という空語遷移を加え、 $d$ では各 $X\in\Gamma\cup\{\bot\}$ を空語遷移で取り除く。

$M$ が $w$ を終状態で受理するなら、新しい機械はその計算を模倣し、状態 $d$ へ移ってスタック全体を空にする。逆に、新しい機械が入力をすべて消費してスタックを空にするには、状態 $d$ へ入らなければならず、その直前には $M$ の受理状態にいる。状態 $d$ には入力を消費する遷移がないため、その時点で入力はすでに空である。したがって、変換前後の受理言語は等しい。

次に、空スタックで受理する PDA $M$ を終状態受理へ変換する。 $Q$ に属さない新しい状態 $s,f$ と、 $\Gamma$ に属さない新しい底記号 $\bot$ をとる。初期スタックを $\bot$ とし、空語遷移で $s$ から $q_0$ へ移るときに $\bot$ を $Z_0\bot$ へ置き換える。 $M$ の遷移をすべて複製し、各 $q\in Q$ について、上端が $\bot$ になったときに空語遷移で $f$ へ移り、 $\bot$ は残す。 $f$ を唯一の受理状態とし、 $f$ からの遷移は置かない。

$M$ が入力全体を消費して元のスタックを空にしたとき、新しい機械の上端は $\bot$ であるため $f$ へ移ることができる。逆に、新しい機械が $f$ で入力全体を消費しているなら、 $f$ へ入る直前には上端が $\bot$ であり、元のスタックは空である。よって、この変換も受理言語を保存する。▨

新しい状態と底記号は、元の状態集合およびスタックアルファベットに属さないものを選ばなければならない。既存の記号を再利用すると、元の計算と受理後のスタック消去を区別することができない場合がある。

3 文脈自由文法から PDA へ

CFG の左端導出を、スタックの上端にある左端記号の展開として実行する。

定理 3.1. 任意の CFG $G$ に対して、 $L(M_G)=L(G)$ を空スタックで受理する PDA $M_G$ を構成することができる。

証明. $G=(V,\Sigma,P,S)$ とする。一状態 $q$ をもち、スタックアルファベットを

\Gamma=V\cup\Sigma

とし、初期スタック記号を $S$ とする PDA $M_G$ を構成する。各生成規則 $A\to\gamma$ に対して

(q,\gamma)\in\delta(q,\varepsilon,A)

とし、各 $a\in\Sigma$ に対して

(q,\varepsilon)\in\delta(q,a,a)

とする。前者は上端の非終端記号を規則の右辺へ置き換え、後者は入力の先頭文字と上端の終端記号が一致するときに両方を取り除く。

入力 $w$ の接頭辞 $x$ をすでに消費し、残りが $y$ で、スタックが $\alpha$ である配置

(q,y,\alpha)

に対して、文形式 $x\alpha$ を対応させる。初期配置では $x=\varepsilon$ 、 $\alpha=S$ であるため、対応する文形式は $S$ である。

生成規則に対応する空語遷移が

(q,y,A\beta)\vdash(q,y,\gamma\beta)

を与えるとき、対応する文形式は

xA\beta\Rightarrow_G x\gamma\beta

と変化する。 $x$ は消費済みの終端語であるため、この導出は左端導出である。終端記号を照合する遷移

(q,ay,a\beta)\vdash(q,y,\beta)

では、消費済み接頭辞が $x$ から $xa$ へ変わるが、対応する文形式は遷移の前後でともに $xa\beta$ であり、文法の導出は進まない。

したがって、 $M_G$ に受理計算

(q,w,S)\vdash^*(q,\varepsilon,\varepsilon)

が存在するなら、遷移列に沿って上の対応を適用することにより

S\Rightarrow_{\mathrm{lm}}^*w

を得る。よって $w\in L(G)$ である。

逆に $w\in L(G)$ とする。命題 1.3により、左端導出

S\Rightarrow_{\mathrm{lm}}^*w

が存在する。左端導出の各生成規則を、上端非終端記号を置き換える空語遷移で順に模倣する。文形式の先頭に終端記号が現れるたび、その文字を入力とスタックから同時に取り除く。左端導出であるため、次に展開する非終端記号より左側の終端記号はすべてこの方法で照合することができる。導出が $w$ に達した後、残る終端記号をすべて照合すると、入力とスタックが同時に空になる。したがって $M_G$ は $w$ を空スタックで受理する。ゆえに $L(M_G)=L(G)$ である。▨

定理 2.3を適用すれば、同じ言語を終状態で受理する PDA も得られる。

4 PDA から文脈自由文法へ

逆向きの構成では、一つのスタック記号を取り除き、その下のスタック部分へ初めて戻るまでの計算区間を、一つの非終端記号で表す。

定義 4.1 (保護された計算区間). PDA $M$ の状態 $p,q$ 、スタック記号 $X$ 、語 $w$ に対して

p\xRightarrow[X]{w}q

で表す関係を保護された計算区間 (protected computation segment) といい、任意のスタック接尾辞 $\beta$ に対して、入力 $w$ をちょうど消費する計算

(p,w,X\beta)\vdash_M^*(q,\varepsilon,\beta)

が存在し、終点より前のすべての配置のスタックが $\rho\beta$ （ $\rho\in\Gamma^+$ ）の形をもつとき、かつそのときに限り $p\xRightarrow[X]{w}q$ と定める。この計算は、最後の一手まで接尾辞 $\beta$ の記号を読み書きしない。

遷移は上端だけを参照するため、ある $\beta$ について保護された計算が存在すれば、同じ遷移列を任意の $\beta$ の上で実行することができる。したがって、定義中の「任意の接尾辞」は一つの接尾辞について確かめても同じ関係を与える。

定理 4.2. 任意の PDA $M$ に対して、 $L(G_M)=L(M)$ を満たす CFG $G_M$ を構成することができる。

証明.定理 2.3によって、 $M$ は空スタックで受理すると仮定してよい。 $M$ を

M=(Q,\Sigma,\Gamma,\delta,q_0,Z_0)

と書く。

各 $p,q\in Q$ と $X\in\Gamma$ に対して、新しい非終端記号

[pXq]

を用意する。非終端記号 $[pXq]$ は入力記号およびスタック記号とは異なる形式的な記号である。さらに新しい開始記号 $S_0$ を用意し、各 $q\in Q$ に対して

S_0\to[q_0Z_0q]

を生成規則に加える。

PDA の遷移

(r,Y_1\cdots Y_k)\in\delta(p,a,X), \qquad a\in\Sigma\cup\{\varepsilon\}

を一つ固定する。 $k\ge 1$ の場合、任意の中間状態

s_1,\ldots,s_{k-1}\in Q

と終状態 $q\in Q$ に対して

[pXq]\to \overline{a}\,[rY_1s_1][s_1Y_2s_2]\cdots [s_{k-1}Y_kq]

という展開規則を加える。ここで、 $a\in\Sigma$ なら $\overline{a}=a$ とし、 $a=\varepsilon$ なら $\overline{a}$ は空語を表す。 $k=0$ の場合には

[pXr]\to\overline{a}

という消去規則を加える。 $Q,\Gamma$ および遷移集合が有限であり、各遷移が有限長のスタック語を押し込むため、この文法の非終端記号と生成規則は有限個である。

次の不変量を証明する。

[pXq]\Rightarrow_{G_M}^*w \quad\Longleftrightarrow\quad p\xRightarrow[X]{w}q.

左から右を、完成した $[pXq]$ -導出木の内部頂点数に関する帰納法で示す。命題 1.3は根を任意の非終端記号とする形で述べてあるため、 $G_M$ の開始記号でない $[pXq]$ を根とする導出木にも適用することができる。根で展開規則を用いたとする。PDA は最初に入力 $a$ を消費するか、 $a=\varepsilon$ の場合には入力を消費せず、

(p,\overline{a}w_1\cdots w_k,X\beta) \vdash (r,w_1\cdots w_k,Y_1\cdots Y_k\beta)

と遷移する。各子の部分木は根の木より小さいため、帰納法の仮定により、 $w_i$ を消費して $Y_i$ を取り除き、状態を一つ前の中間状態から次の中間状態へ移す保護された計算が存在する。各子部分木に対応する保護された計算を左から順に連結すると、 $X$ を取り除いて状態 $q$ に至る保護された計算を得る。消去規則の場合には、最初の一遷移が $X$ を直ちに取り除くため主張が成り立つ。

右から左を、保護された計算の遷移回数に関する帰納法で示す。 $p\xRightarrow[X]{w}q$ を与える計算の最初の遷移を

(r,Y_1\cdots Y_k)\in\delta(p,a,X)

とする。 $k=0$ ならば、この一遷移で接尾辞 $\beta$ が露出する。保護された計算はその時点で終わらなければならないため $q=r$ 、 $w=\overline a$ であり、消去規則が $[pXq]\Rightarrow^*w$ を与える。

$k\ge 1$ とする。計算は接尾辞 $\beta$ に触れずに $Y_1\cdots Y_k$ をすべて取り除く。各 $i=1,\ldots,k$ について、スタック全体が初めて $Y_{i+1}\cdots Y_k\beta$ に一致する時点をとる。ただし $i=k$ では、スタックが初めて $\beta$ になる終点をとる。スタック記号が重複する場合があるため、上端の記号ではなくスタック語全体で時点を定める。このような時点は、スタックが上端からしか変更されず、最終的に $\beta$ へ戻るため必ず存在する。その時点の状態を $s_i$ とし、 $s_k=q$ とする。最初の遷移後からこれらの時点までに消費される入力を順に $w_1,\ldots,w_k$ と書くと、

w=\overline a w_1\cdots w_k

であり、

r\xRightarrow[Y_1]{w_1}s_1,\quad s_1\xRightarrow[Y_2]{w_2}s_2,\quad\ldots,\quad s_{k-1}\xRightarrow[Y_k]{w_k}q

が成り立つ。各区間は元の計算より遷移回数が少ないため、帰納法の仮定から

[rY_1s_1]\Rightarrow^*w_1,\quad\ldots,\quad [s_{k-1}Y_kq]\Rightarrow^*w_k

を得る。対応する展開規則を最初に適用し、各小区間に対応する導出を続ければ $[pXq]\Rightarrow^*w$ を得る。以上の二方向の帰納法によって、不変量の証明が完了する。

最後に、

\begin{aligned} w\in L(G_M) &\Longleftrightarrow \text{ある }q\in Q\text{ について }[q_0Z_0q]\Rightarrow^*w\\ &\Longleftrightarrow \text{ある }q\in Q\text{ について }q_0\xRightarrow[Z_0]{w}q\\ &\Longleftrightarrow M\text{ が }w\text{ を空スタックで受理する} \end{aligned}

となる。よって $L(G_M)=L(M)$ である。▨

二つの変換をまとめる。

定理 4.3. 有限アルファベット $\Sigma$ 上の言語 $L\subseteq\Sigma^*$ について、次の条件は同値である。

$L$ はある文脈自由文法によって生成される。
$L$ はある非決定性 PDA によって空スタックで受理される。
$L$ はある非決定性 PDA によって終状態で受理される。

証明.(1) $\Rightarrow$ (2)は定理 3.1による。(2) $\Leftrightarrow$ (3)は定理 2.3による。(3) $\Rightarrow$ (1)は、終状態受理を空スタック受理へ変換した後、定理 4.2を適用すれば従う。▨

5 正規言語との関係

先行記事の有限オートマトンは、状態遷移を右端の非終端記号の展開として書き直すことができる。これにより、正規言語が文脈自由言語であることが従う。

命題 5.1. $\Sigma$ 上の任意の正規言語 $L$ に対して、 $L(G)=L$ となる CFG $G$ が存在する。

証明.§E15.2 定義 1により、 $L=L(A)$ となる DFA $A=(Q,\Sigma,\delta,q_\ell,F)$ を取る。 $Q=\{q_1,\ldots,q_n\}$ と番号づけ、 $Q$ 、 $\Sigma$ のいずれにも属さない新しい非終端記号 $B_1,\ldots,B_n$ を用意する。 $V:=\{B_1,\ldots,B_n\}$ とし、生成規則を

B_i\to aB_j\quad(a\in\Sigma,\ \delta(q_i,a)=q_j), \qquad B_i\to\varepsilon\quad(q_i\in F)

とする。開始記号は $B_\ell$ とする。 $Q$ と $\Sigma$ が有限であるから、規則は有限個である。

以下では、§E15.1 補題 1.3の後半の形 $\widehat{\delta}(q,au)=\widehat{\delta}(\delta(q,a),u)$ を用いる。

各 $i$ と各 $w\in\Sigma^*$ について

B_i\Rightarrow_G^*w \quad\Longleftrightarrow\quad \widehat{\delta}(q_i,w)\in F

を、 $w$ の長さに関する帰納法で示す。

$w=\varepsilon$ とする。 $B_i$ を左辺とする規則のうち、 $B_i\to aB_j$ を適用した文形式は先頭に終端記号 $a$ をもち、以後の適用でその $a$ が消えることはない。したがって $B_i\Rightarrow_G^*\varepsilon$ となるのは $B_i\to\varepsilon$ が規則である場合に限り、それは $q_i\in F$ と同値である。一方 $\widehat{\delta}(q_i,\varepsilon)=q_i$ であるから、両辺は同値である。

$w=au'$ とする。 $B_i\Rightarrow_G^*au'$ が成り立つとする。最初に適用する規則が $B_i\to\varepsilon$ であれば文形式は $\varepsilon$ となり、 $au'\ne\varepsilon$ に達することはない。よって最初の規則は $B_i\to aB_j$ の形であり、先頭の終端記号が一致するため $\delta(q_i,a)=q_j$ である。残りの導出は $B_j\Rightarrow_G^*u'$ を与える。逆に、 $\delta(q_i,a)=q_j$ かつ $B_j\Rightarrow_G^*u'$ ならば、 $B_i\to aB_j$ を最初に適用して $B_i\Rightarrow_G^*au'$ を得る。帰納法の仮定により $B_j\Rightarrow_G^*u'$ は $\widehat{\delta}(q_j,u')\in F$ と同値であり、上で示した等式により

\widehat{\delta}(q_j,u')=\widehat{\delta}(\delta(q_i,a),u')=\widehat{\delta}(q_i,au')

である。よって両辺は同値である。

$i=\ell$ とすれば、 $w\in L(G)$ と $\widehat{\delta}(q_\ell,w)\in F$ が同値である。§E15.1 定義 1.4により後者は $w\in L(A)=L$ と同値であるから、 $L(G)=L$ である。▨

命題 5.1と定理 4.3により、正規言語の全体は文脈自由言語の全体に含まれる。この包含が真であることは、§E15.2 命題 5.5と例 1.4 (a の並びの後に同数の b が続く言語)から従う。

6 具体例

$a$ と $b$ の個数を照合する言語に対して、専用の PDA を直接構成する。定理 3.1の一般構成とは別の機械である。

命題 6.1. 言語

\{a^n b^n:n\ge 0\}

を終状態で受理する PDA が存在する。

証明. 新しい底記号を $\bot$ 、個数を記録する記号を $X$ とする。初期状態 $q_s$ から、入力を消費しない二つの選択を置く。一つは空語を受理する状態 $q_f$ へ移る選択であり、もう一つは $a$ を読む状態 $q_a$ へ移る選択である。

$q_a$ では $a$ を一文字読むたびに $X$ を一つ積む。最初の $b$ を読むときに $q_b$ へ移り、 $X$ を一つ取り除く。 $q_b$ では $b$ を一文字読むたびに $X$ を一つ取り除く。 $q_b$ で上端が $\bot$ になったときに、空語遷移で $q_f$ へ移る。 $q_f$ から遷移は置かない。

定義 2.1の遷移関数は入力の残りを参照しないため、「入力を読み終えた」という条件を遷移の側に書くことはできない。上の遷移は入力が残っていても起こり得るが、 $q_f$ から出る遷移が一つもないため、その場合は入力を消費し切ることができず受理に至らない。定義 2.2が入力全体の消費を要求することが、この点を担っている。

$q_a$ で $a$ を $k$ 個読んだ直後のスタックが $X^k\bot$ であることは $k$ に関する帰納法で従う。 $q_b$ で $b$ を $j$ 個読んだ後、 $j\le k$ ならスタックは $X^{k-j}\bot$ である。 $j>k$ なら取り除く $X$ が存在しないため計算は停止する。また、 $q_b$ では $a$ を読む遷移がなく、 $q_a$ へ戻る遷移もない。したがって、空語以外で受理される語は $a^k b^k$ に限る。

逆に、 $a^n b^n$ では $n=0$ のとき初期状態から直接 $q_f$ へ移る。 $n>0$ のとき、 $a$ を読むたびに $X$ を積み、続く $b$ を読むたびに $X$ を取り除けば、入力の終端で上端が $\bot$ になり $q_f$ へ移ることができる。よって、受理言語はちょうど $\{a^n b^n:n\ge0\}$ である。▨

7 文脈自由言語の限界

定理 4.3は、二つの記述方法が同じ言語の範囲を定めることを述べる。その範囲がすべての言語を尽くすわけではないことを、構文木の形に対する制約から導く。

頂点 $v$ の成果 $\mathrm{yield}(v)$ は定義 1.2で定めた。あわせて、 $v$ から葉へ至る道の辺数の最大値を $v$ の高さといい、根の高さを木の高さという。

補題 7.1. CFG $G=(V,\Sigma,P,S)$ に対して

b:=\max\bigl(\{2\}\cup\{|\gamma|:A\to\gamma\in P\}\bigr)

と置く。右辺の集合は $2$ を要素にもつ有限集合であるから、 $P=\varnothing$ の場合を含めて $b$ は定まり、 $b\ge 2$ である。また、 $P$ の各規則 $A\to\gamma$ について $|\gamma|\le b$ である。 $G$ の構文木の任意の頂点 $v$ について、 $v$ の高さが $h$ ならば $|\mathrm{yield}(v)|\le b^{h}$ である。

証明. $h$ に関する帰納法を用いる。

$h=0$ のとき、 $v$ は葉であり、定義 1.2によって終端記号または $\varepsilon$ で標識される。したがって $|\mathrm{yield}(v)|\le 1=b^0$ である。

$h\ge 1$ とする。 $v$ の子を左から $u_1,\ldots,u_k$ とする。 $v$ が規則 $A\to\gamma$ に対応するならば $k=|\gamma|\le b$ であり、 $v$ が規則 $A\to\varepsilon$ に対応するならば $k=1\le b$ である。各 $u_i$ の高さは高々 $h-1$ であるから、帰納法の仮定により $|\mathrm{yield}(u_i)|\le b^{h-1}$ である。 $\mathrm{yield}(v)$ は $\mathrm{yield}(u_1)\cdots\mathrm{yield}(u_k)$ に等しいから

|\mathrm{yield}(v)|\le k\,b^{h-1}\le b\cdot b^{h-1}=b^{h}

である。▨

非終端記号は有限個であるから、成果が長い構文木には、根から葉への一本の道の上に同じ非終端記号が二度現れる。その二つの頂点にはさまれた部分を繰り返すことができる。

定理 7.2 (文脈自由言語のポンピング補題). $L$ を文脈自由言語とする。このとき、 $L$ だけに依存する定数 $N\ge 1$ が存在して、 $|w|\ge N$ を満たす任意の $w\in L$ は

w=uvxyz \qquad(u,v,x,y,z\in\Sigma^*)

の形に分解することができ、次の三条件を満たす。

$|vxy|\le N$ 。
$vy\ne\varepsilon$ 。
すべての $i\ge 0$ について $uv^ixy^iz\in L$ 。

証明. $L=L(G)$ となる CFG $G=(V,\Sigma,P,S)$ を取り、補題 7.1の $b$ を用いて

N:=b^{|V|+1}

と置く。 $w\in L$ が $|w|\ge N$ を満たすとする。

命題 1.3により、成果が $w$ である構文木が存在する。そのような構文木の頂点数は正の整数であるから、頂点数が最小であるものを一つ取り、 $T$ と書く。

$T$ の根から葉へ至る道のうち、辺数が最大であるものを一つ取り、 $\pi$ と書く。その辺数を $h$ とする。根から葉へ至る道の辺数の最大値は根の高さであるから、補題 7.1により $b^{h}\ge|w|\ge N=b^{|V|+1}$ である。 $b\ge 2$ であるから $h\ge|V|+1$ である。

$\pi$ 上の頂点は $h+1$ 個ある。末端の葉を除く $h$ 個は子をもつため、定義 1.2 条件 (c)または定義 1.2 条件 (d)により非終端記号で標識される。 $h\ge|V|+1$ であるから、 $\pi$ 上で葉に近い側から非終端記号で標識された頂点を $|V|+1$ 個取ることができる。非終端記号は $|V|$ 種類であるから、鳩の巣原理により、この $|V|+1$ 個のうち二つは同じ非終端記号 $A$ で標識される。 $\pi$ 上で上にある方を $r_1$ 、下にある方を $r_2$ とする。

$\pi$ は根から葉へ至る道のうち辺数が最大であるから、 $\pi$ 上の頂点 $p$ の高さは、 $\pi$ のうち $p$ より下にある部分の辺数に等しい。実際、 $p$ を根とする部分木に、 $p$ から葉へ至るより長い道があれば、 $\pi$ の $p$ より下を差し替えて $\pi$ より長い道を得るからである。 $r_1$ は $\pi$ 上で葉から数えて高々 $|V|+1$ 番目の非終端記号頂点であるから、 $\pi$ のうち $r_1$ より下にある部分の辺数は高々 $|V|+1$ であり、 $r_1$ の高さは高々 $|V|+1$ である。したがって補題 7.1により

|\mathrm{yield}(r_1)|\le b^{|V|+1}=N

である。

$r_2$ は $r_1$ の真の子孫であるから、 $\mathrm{yield}(r_2)$ は $\mathrm{yield}(r_1)$ の連続部分語であり、

\mathrm{yield}(r_1)=v\,\mathrm{yield}(r_2)\,y

と一意に分かれる。 $x:=\mathrm{yield}(r_2)$ と置く。同様に $\mathrm{yield}(r_1)$ は $w$ の連続部分語であるから $w=u\,\mathrm{yield}(r_1)\,z$ と分かれる。以上により $w=uvxyz$ であり、 $|vxy|=|\mathrm{yield}(r_1)|\le N$ であるから条件 (a)が成り立つ。

ここで、二つの木を用意する。 $T$ の $r_1$ を根とする部分木を、 $r_2$ を根とする部分木で置き換えて得られる木を $T^-$ とする。また、 $T$ の $r_2$ を根とする部分木を、 $r_1$ を根とする部分木の複製で置き換えて得られる木を $T^+$ とする。 $r_1$ と $r_2$ はともに $A$ で標識されるから、いずれの置き換えでも定義 1.2の四条件は保たれ、 $T^-$ と $T^+$ はともに構文木である。成果はそれぞれ $uxz$ と $uv^2xy^2z$ である。この二つの構成は、以下の仮定に依存しない。

条件 (b)を示す。 $v=y=\varepsilon$ と仮定する。このとき $T^-$ の成果は $uxz=uvxyz=w$ であり $T$ と等しい。一方、 $r_2$ は $r_1$ の真の子孫であるから、 $T^-$ の頂点数は $T$ の頂点数より真に少ない。これは $T$ の最小性に反する。よって $vy\ne\varepsilon$ である。

条件 (c)を示す。 $i=0$ の場合、 $T^-$ が成果 $uxz$ の構文木を与える。 $i\ge 1$ の場合、 $T$ から $T^+$ を作る操作を繰り返す。複製された部分木の中には $r_2$ に対応する頂点が再び現れるため、同じ操作をその頂点に対して適用することができる。操作の前後で成果は $uv^kxy^kz$ から $uv^{k+1}xy^{k+1}z$ へ変わり、 $T$ の成果が $uvxyz$ であることから、操作を $i-1$ 回行えば成果 $uv^ixy^iz$ の構文木を得る。いずれの場合も命題 1.3により $uv^ixy^iz\in L(G)=L$ である。▨

補題の条件 (a)は、繰り返す部分が語の中で近い位置に収まることを保証する。三つの区間の個数を同時に照合する言語では、この制約が矛盾を導く。

命題 7.3. $\Sigma=\{a,b,c\}$ とする。言語

L=\{a^nb^nc^n:n\ge 0\}

は文脈自由言語ではない。

証明. $L$ が文脈自由であると仮定し、定理 7.2 (文脈自由言語のポンピング補題)の定数 $N$ を取る。 $w:=a^Nb^Nc^N$ と置くと $w\in L$ かつ $|w|=3N\ge N$ であるから、三条件を満たす分解 $w=uvxyz$ が存在する。

$w$ において、 $a$ が占める位置は $1$ から $N$ 、 $c$ が占める位置は $2N+1$ から $3N$ である。 $a$ の位置と $c$ の位置をともに含む連続部分語の長さは $(2N+1)-N+1=N+2$ 以上であり、定理 7.2 条件 (a)の $|vxy|\le N$ に反する。したがって、連続部分語 $vxy$ は $a$ と $c$ の両方を含むことはない。

よって $vy$ に現れる文字は $\{a,b\}$ または $\{b,c\}$ のいずれかに含まれ、 $a,b,c$ のうち少なくとも一種の文字 $\sigma$ は $vy$ に現れない。

$i=2$ を取る。 $w=uvxyz$ であるから、 $uv^2xy^2z$ における各文字の個数は、 $w$ における個数に $vy$ における個数を加えたものである。したがって $\sigma$ の個数は $N$ のままである。一方、定理 7.2 条件 (b)により $vy\ne\varepsilon$ であるから、 $vy$ に現れる文字 $\tau$ が存在し、 $uv^2xy^2z$ における $\tau$ の個数は $N$ より真に大きい。 $\sigma\ne\tau$ であるから、 $uv^2xy^2z$ では三種の文字の個数が等しくない。ゆえに $uv^2xy^2z\notin L$ であり、これは定理 7.2 条件 (c)に反する。よって $L$ は文脈自由言語ではない。▨

命題 5.1は正規言語の全体が文脈自由言語の全体に含まれることを示し、§E15.2 命題 5.5と例 1.4 (a の並びの後に同数の b が続く言語)はこの包含が真であることを示す。命題 7.3は、PDA の表現力にも真の限界があることを示す。より強い計算モデルは次の記事で扱う。

8 つまずいたら

CFG の空語規則 $A\to\varepsilon$ は、非終端記号 $A$ を消去する規則である。空言語を生成する規則ではない。
PDA の空語遷移は入力を消費しないが、スタックを書き換えることができる。空語遷移を無制限に許しても、受理には入力全体の消費が必要である。
CFG から PDA への変換は、スタックの上端を左端として規則の右辺を同じ順序で置く。本記事と反対に右端を上端とする規約では、右辺を逆順に積む必要がある。
PDA から CFG への変換における $[pXq]$ は、状態 $p$ から状態 $q$ へ移る任意の計算を表すのではない。 $X$ の下の接尾辞へ触れずに $X$ をちょうど取り除く計算区間だけを表す。
終状態受理と空スタック受理の変換では、新しい底記号が元のスタック記号と異なることが必要である。
定理 7.2 (文脈自由言語のポンピング補題)は文脈自由言語が満たす必要条件を述べる。条件を満たすことから文脈自由性を結論することはできない。
定理 7.2 (文脈自由言語のポンピング補題)が与える $N$ の値は、選んだ文法によって変わる。定理は「そのような $N$ が存在する」と述べるだけであるから、非文脈自由性を示す際は $N$ を任意の定数として扱い、 $N$ に依存する語 $w$ を選ぶ。

9 演習

問題 9.1.

$S\to aSb\mid SS\mid\varepsilon$ の構文木を一つ描き、成果が $aabbab$ となる左端導出を構成せよ。
定理 3.1の PDA が、規則 $S\to\varepsilon$ をもつ文法について空語を受理する計算を配置の列で示せ。
定理 4.2の生成規則で、中間状態をすべて列挙する必要がある理由を説明せよ。状態を固定すると失われる計算の例を構成せよ。
終状態受理から空スタック受理への変換で、排出状態 $d$ が入力文字を消費する遷移をもつと受理言語が変わり得ることを示せ。
定理 7.2 条件 (a) $|vxy|\le N$ を落とすと、命題 7.3の証明のどこが成り立たなくなるかを述べよ。
定理 7.2 (文脈自由言語のポンピング補題)の証明では、構文木 $T$ を頂点数が最小であるものに取った。この最小性を用いた箇所を指摘し、最小性を仮定しない場合に導くことができなくなる主張を述べよ。

解答 (演習の要点).

一例は、根 $S$ の子を $S,S$ とし、左の子から $S\to aSb$ を二回、 $S\to\varepsilon$ を一回適用し、右の子から $S\to aSb$ と $S\to\varepsilon$ を適用した構文木である。対応する左端導出は $S\Rightarrow SS\Rightarrow aSbS\Rightarrow aaSbbS\Rightarrow aabbS\Rightarrow aabbaSb\Rightarrow aabbab$ であり、各段で最も左の非終端記号だけを展開している。
規則 $S\to\varepsilon$ に対応する空語遷移 $(q,\varepsilon)\in\delta(q,\varepsilon,S)$ により、 $(q,\varepsilon,S)\vdash(q,\varepsilon,\varepsilon)$ となる。入力は最初から空であり、スタックも空になるため、空語が空スタックで受理される。
遷移が $Y_1\cdots Y_k$ を積んだ時点では、各 $Y_i$ を取り除き終えたときの状態が、その後の計算によって初めて決まるからである。文法の規則は計算より前に固定されるため、中間状態のすべての組合せを規則として用意し、実際の計算に一致しない組合せは終端語を導かない形で残す。例として、二状態 $r,s$ と遷移 $\delta(r,a,Y)\ni(r,\varepsilon)$ 、 $\delta(r,b,Y)\ni(s,\varepsilon)$ 、 $\delta(s,b,Y)\ni(s,\varepsilon)$ をもつ機械で、スタック $YY$ を取り除く計算を考える。入力 $aa$ では一つ目の $Y$ の除去が状態 $r$ で終わり、入力 $bb$ では状態 $s$ で終わる。中間状態を $r$ に固定した規則だけを許すと、 $bb$ を消費する計算に対応する導出が失われる。
排出状態 $d$ に入力文字を消費する遷移があると、受理状態へ到達した後に残った入力を排出中に消費することができてしまう。たとえば、一文字 $a$ を読んで受理状態へ移る機械 $M$ の受理言語は $\{a\}$ である。変換後の機械の $d$ に $b$ を読みながらスタック記号を取り除く遷移を加えると、入力 $ab$ でも、 $a$ を読んで受理状態に至り、 $d$ で $b$ を消費しながらスタックを空にすることができるため、 $ab$ が受理され、受理言語が変わる。
$vxy$ の長さに制限がなければ、 $vxy$ が $a$ の区間と $c$ の区間の両方に交わることを排除することができない。その場合、 $vy$ が三種の文字すべてを含み得るため、 $uv^2xy^2z$ で三つの個数が同時に等しく増える可能性が残り、矛盾を導くことができない。
最小性は定理 7.2 条件 (b) $vy\ne\varepsilon$ の証明だけに用いた。最小性を仮定しない場合、 $v=y=\varepsilon$ となる分解が生じ得る。このとき定理 7.2 条件 (c)はすべての $i$ について $w$ 自身を与えるだけであり、補題は非文脈自由性の証明に用いることができない主張になる。

▨

§E15.3文脈自由言語

1 文法、導出、構文木

2 Pushdown automaton と受理方式

3 文脈自由文法から PDA へ

4 PDA から文脈自由文法へ

5 正規言語との関係

6 具体例

7 文脈自由言語の限界

9 演習

参考文献

前提記事