文脈自由言語 | 計算理論

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. 開始記号を $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)

となることをいう。

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

定理 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 へ

次の定理で構成する 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$ が存在する。

証明.§E18.2 定義 1.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$ が有限であるから、規則は有限個である。

以下では、§E18.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$ が同値である。§E18.1 定義 1.4により後者は $w\in L(A)=L$ と同値であるから、 $L(G)=L$ である。▨

命題 5.1と定理 4.3により、正規言語の全体は文脈自由言語の全体に含まれる。この包含が真であることは、§E18.2 命題 5.5と例 1.4から従う。

6 具体例

言語 $\{a^nb^n:n\ge 0\}$ を受理する専用の PDA を直接構成する。この 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により、文脈自由文法で生成される言語のクラスと、PDA で受理される言語のクラスは一致する。このクラスがすべての言語を含むわけではないことを、構文木の形に対する制約から導く。

頂点 $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)により、繰り返す部分語 $v,y$ は、長さ $N$ 以下の連続部分語 $vxy$ の中にある。 $a,b,c$ をこの順に同数ずつ並べた語からなる言語では、この制約から矛盾が導かれる。

命題 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により正規言語の全体が文脈自由言語の全体に含まれることが示され、§E18.2 命題 5.5と例 1.4によりこの包含が真であることが示される。命題 7.3により、PDA で受理することができない言語が存在することが示される。

8 演習

問題 8.1.

$S\to aSb\mid SS\mid\varepsilon$ の構文木を一つ描き、成果が $aabbab$ となる左端導出を構成せよ。
定理 3.1の PDA が、規則 $S\to\varepsilon$ をもつ文法について空語を受理する計算を配置の列で示せ。
空スタックで受理する PDA $M$ を、状態集合 $\{r,s\}$ 、スタック記号 $\{Z,Y\}$ 、初期状態 $r$ 、初期スタック記号 $Z$ 、遷移 $(r,YY)\in\delta(r,\varepsilon,Z)$ 、 $(r,\varepsilon)\in\delta(r,a,Y)$ 、 $(s,\varepsilon)\in\delta(r,b,Y)$ 、 $(s,\varepsilon)\in\delta(s,b,Y)$ で定める。 $M$ が空スタックで受理する言語を求めよ。また、定理 4.2の生成規則のうち、中間状態 $s_1$ を $r$ に固定した展開規則だけを残した文法の言語を求め、二つの言語が異なることを示せ。
終状態受理から空スタック受理への変換で、排出状態 $d$ が入力文字を消費する遷移をもつと受理言語が変わり得ることを示せ。
言語 $L$ が「定数 $N$ が存在し、 $|w|\geq N$ を満たす任意の $w\in L$ が定理 7.2 条件 (b)と定理 7.2 条件 (c)を満たす分解 $w=uvxyz$ をもつ」という性質をもつとき、 $L$ は弱いポンピング性質をもつという。定理 7.2 条件 (a)を課さない点だけが定理 7.2と異なる。 $\{a^nb^nc^n:n\geq0\}$ は弱いポンピング性質をもたないことを示せ。一方、 $L'=\{a^nb^mc^nd^m:n,m\geq0\}$ は弱いポンピング性質をもつが、定理 7.2により文脈自由でないことを示せ。
文法 $G$ を $S\to SS\mid S\mid a$ とし、 $w=aaaa$ とする。定理 7.2の証明の $b=2$ 、 $N=b^{|V|+1}=4$ について、成果が $w$ である構文木 $T$ で、証明と同じ手順（辺数が最大の道 $\pi$ を取り、葉に近い側から $|V|+1$ 個の非終端記号頂点のうち同じ記号をもつ二つを $r_1,r_2$ とする）を適用すると $v=y=\varepsilon$ となるものを構成せよ。また、頂点数が最小の構文木に同じ手順を適用すると $vy\neq\varepsilon$ となることを、一つの最小な構文木について確かめよ。

解答 (演習の要点).

一例は、根 $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)$
となる。入力は最初から空であり、スタックも空になるため、空語が空スタックで受理される。
$M$ は最初に入力を消費せず $Z$ を $YY$ に置き換えるほかに遷移をもたないので、受理計算は $(r,w,Z)\vdash(r,w,YY)$ から始まり、二つの $Y$ を一文字ずつ消費して取り除く。状態 $r$ では $a$ を読むと $r$ に、 $b$ を読むと $s$ に移り、状態 $s$ では $b$ だけを読むことができる。したがって受理計算は $r\xrightarrow{a}r\xrightarrow{a}r$ 、 $r\xrightarrow{a}r\xrightarrow{b}s$ 、 $r\xrightarrow{b}s\xrightarrow{b}s$ の三通りであり、空スタックで受理する言語は $\{aa,ab,bb\}$ である。

定理 4.2の文法の規則は、 $S_0\to[rZq]$ （ $q\in\{r,s\}$ ）、展開規則 $[rZq]\to[rYs_1][s_1Yq]$ （ $s_1,q\in\{r,s\}$ ）、消去規則 $[rYr]\to a$ 、 $[rYs]\to b$ 、 $[sYs]\to b$ である。 $s_1=r$ に固定すると、展開規則は $[rZr]\to[rYr][rYr]$ と $[rZs]\to[rYr][rYs]$ だけになる。 $[rYr]$ と $[rYs]$ はそれぞれ $a$ と $b$ だけを導き、 $[sZq]$ と $[sYr]$ を左辺にもつ規則はないので、 $[rZr]$ は $aa$ だけを、 $[rZs]$ は $ab$ だけを導く。よって固定した文法の言語は $\{aa,ab\}$ であり、 $M$ の言語と異なる。失われた語 $bb$ の導出 $S_0\Rightarrow[rZs]\Rightarrow[rYs][sYs]\Rightarrow bb$ では、一つ目の $Y$ を取り除き終えたときの状態が $s$ であり、展開規則の中間状態に $s$ が必要である。
排出状態 $d$ に入力文字を消費する遷移があると、受理状態へ到達した後に残った入力を排出中に消費することができてしまう。たとえば、一文字 $a$ を読んで受理状態へ移る機械 $M$ の受理言語は $\{a\}$ である。変換後の機械の $d$ に $b$ を読みながらスタック記号を取り除く遷移を加えると、入力 $ab$ でも、 $a$ を読んで受理状態に至り、 $d$ で $b$ を消費しながらスタックを空にすることができるため、 $ab$ が受理され、受理言語が変わる。
$L_3=\{a^nb^nc^n:n\geq0\}$ が弱いポンピング性質をもつと仮定し、その定数を $N$ とする。 $w=a^Nb^Nc^N$ の分解 $w=uvxyz$ で $vy\neq\varepsilon$ を満たすものを取る。 $v$ が二種類以上の文字を含むならば、 $v^2$ の中にある文字の後に前の種類の文字が現れるので、 $uv^2xy^2z$ は $a^*b^*c^*$ の形でなく $L_3$ に属さない。 $y$ についても同様である。 $v$ と $y$ がそれぞれ一種類の文字だけからなるならば、 $vy$ に現れる文字は高々二種類であり、 $vy\neq\varepsilon$ であるから、 $uv^2xy^2z$ では三つの文字の個数のうち少なくとも一つが増え、少なくとも一つが変わらないので $L_3$ に属さない。よって $L_3$ は弱いポンピング性質をもたない。すなわち $L_3$ が文脈自由でないことは、定理 7.2 条件 (a)を用いなくても示すことができる。

$L'$ について $N=1$ とする。 $w=a^nb^mc^nd^m\in L'$ が $|w|\geq1$ を満たすとき、 $n\geq1$ ならば $u=\varepsilon$ 、 $v=a$ 、 $x=a^{n-1}b^mc^{n-1}$ 、 $y=c$ 、 $z=d^m$ とおくと $uv^ixy^iz=a^{n-1+i}b^mc^{n-1+i}d^m\in L'$ である。 $n=0$ ならば $m\geq1$ であり、 $v=b$ 、 $y=d$ として同様である。よって $L'$ は弱いポンピング性質をもつ。

$L'$ が文脈自由であると仮定し、定理 7.2の定数を $N$ とする。 $w=a^Nb^Nc^Nd^N$ の分解を取ると、 $|vxy|\leq N$ であるから、 $vxy$ は $a$ と $c$ の両方を含まず、 $b$ と $d$ の両方も含まない。 $v$ または $y$ が二種類以上の文字を含むならば、前段と同じ理由で $uv^2xy^2z\notin L'$ である。そうでなければ、 $vy\neq\varepsilon$ に現れる文字の種類 $e$ を一つ取ると、 $e$ と対になる文字（ $a$ と $c$ 、 $b$ と $d$ ）は $vy$ に現れないので、 $uv^2xy^2z$ では $e$ の個数は増え、対になる文字の個数は変わらない。よって $uv^2xy^2z\notin L'$ であり、定理 7.2 条件 (c)に反する。したがって $L'$ は文脈自由でない。この証明では、対になる文字の区間が $N$ 以上離れていることを定理 7.2 条件 (a)とともに用いた。
文法の右辺の長さの最大値は $2$ であり、 $|V|=1$ である。最小な構文木の例として、根 $r$ に規則 $S\to SS$ を適用し、その二つの子 $s_1,s_2$ にも $S\to SS$ を適用し、四つの孫 $s_{11},s_{12},s_{21},s_{22}$ に $S\to a$ を適用した木 $T_0$ を取る。この木は $S\to S$ を含まず、四つの $a$ の葉と七つの非終端記号頂点からなる。 $T_0$ の頂点数が最小であることを確かめる。成果が $aaaa$ である任意の構文木では、空語を生む規則がないので葉はちょうど四つの $a$ であり、各葉の親は規則 $S\to a$ を適用した頂点であるから、そのような頂点は四つある。各頂点の子は一つまたは二つであり、葉が四つの根付き木では子を二つもつ頂点の個数は葉の個数より一つ少ないので、 $S\to SS$ を適用した頂点はちょうど三つある。残りの頂点は $S\to S$ を適用した頂点であるから、頂点数は $4+4+3=11$ に $S\to S$ の頂点の個数を加えたものである。 $T_0$ は $S\to S$ を含まないので、頂点数 $11$ は最小である。根から葉への道の辺数の最大値は $3$ であり、 $\pi$ として $r,s_1,s_{11}$ と葉を通る道を取る。葉に近い側の二つの非終端記号頂点は $s_{11}$ と $s_1$ であり、ともに $S$ であるから $r_1=s_1$ 、 $r_2=s_{11}$ である。 $\mathrm{yield}(s_1)=aa$ 、 $\mathrm{yield}(s_{11})=a$ であるから $u=\varepsilon$ 、 $v=\varepsilon$ 、 $x=a$ 、 $y=a$ 、 $z=aa$ であり、 $vy=a\neq\varepsilon$ 、 $|vxy|=2\leq4$ である。

次に、 $T_0$ の $s_{11}$ と葉の間に $S\to S$ を適用した頂点 $t$ を挿入した木 $T$ を作る。すなわち $s_{11}$ の唯一の子を $t$ とし、 $t$ の唯一の子を葉 $a$ とする。 $T$ の成果は $aaaa$ のままであり、根から葉への道の辺数の最大値は $4$ で、それを与える道は $r,s_1,s_{11},t$ と葉を通るものだけである。葉に近い側の二つの非終端記号頂点は $t$ と $s_{11}$ であり、ともに $S$ であるから $r_1=s_{11}$ 、 $r_2=t$ である。 $\mathrm{yield}(s_{11})=\mathrm{yield}(t)=a$ であるから $v=y=\varepsilon$ となる。 $T$ の頂点数は $T_0$ より多く、 $T$ の $r_1$ を根とする部分木を $r_2$ を根とする部分木で置き換えると $T_0$ に戻る。これが定理 7.2の証明で最小性により $v=y=\varepsilon$ を排除する議論である。

▨

§E18.3文脈自由言語

1 文法、導出、構文木

2 Pushdown automaton と受理方式

3 文脈自由文法から PDA へ

4 PDA から文脈自由文法へ

5 正規言語との関係

6 具体例

7 文脈自由言語の限界

8 演習

参考文献

前提記事