本質的に曖昧な文脈自由言語 - ｼﾞｮｲｼﾞｮｲｼﾞｮｲ

本質的に曖昧な文脈自由言語が存在するという事実は色んなところで何度も目にしてきたのですが、証明を見たことが無かったのでここで紹介します。

流れは大体 [1] と同じですが、補題の証明はオリジナルも混ざってます（本質的には同じだとは思います）（間違ってたら教えてください）

今回本質的に曖昧だと示すのは $L = \{ a^{i} b^{j} c^{k} \mid i, j, k \ge 1, i = j \lor j = k \}$ です。（これが文脈自由であることは簡単なので省略します）

ちなみに、これは計算理論の基礎 [2] （めっちゃいい本）の第2版の演習問題 2.29 です。（本に答えは載っていません）

めちゃくちゃ難しいと思うのですが自信のある人は考えてみてください（僕は分かりませんでした）

少しずつ補題を証明していく形式なので、少しずつ読んで考えてみるのも面白いかもしれません。（最後のステップだけでも普通に難しいと思います）

基本的な記法と定義

文脈自由文法を非終端記号 $V_{N} = \{ A_{1}, A_{2},... ,A_{n} \}$ 、終端記号 $V_{T}$ 、生成規則 $R$ 、開始記号 $A_{n}$ の組 $G = ( V_{N}, V_{T}, R, A_{n} )$ で定義します。

生成規則を $A_{i} \rightarrow \alpha_{1}... \alpha_{k}$ のように表します。

生成規則を 0 回以上適用して新しい列を生成することを $A_{i} \rightarrow^{*} \alpha_{1}... \alpha_{k}$ のように表します。

生成規則を 1 回以上適用して新しい列を生成することを $A_{i} \rightarrow^{+} \alpha_{1}... \alpha_{k}$ のように表します。

文法 $G$ が生成する言語を $L(G)$ と表します。

$x, y, w$ は終端記号の列を表すメタ変数とします。

文法 $G$ が既約であるとは、任意の非終端記号 $A_{i}$ について導出の過程で $A_{i}$ を使って言語の要素を導出できることとします。（つまり、開始記号からある非終端記号に到達できなかったり、ある非終端記号から無限ループやデッドエンドに陥って語を生成できないといったことがないということです。）

証明

補題0

任意の曖昧でない文脈自由文法 $G = ( V_{N}, V_{T}, R, A_{n} )$ について、 $L(G') = L(G)$ となる既約な曖昧でない文脈自由文法 $G'$ が存在する。

補題0の証明

到達できない記号や無限ループやデッドエンドに陥る非終端記号を取り除くだけでよいです。

具体的には

$V_{N}^{*} = \{ A_i \mid ( \exists x,y\, s.t.\, A_{n} \rightarrow^{*} x A_i y ) \land ( \exists w\, s.t.\, A_i \rightarrow^{*} w ) \}$ とすると、 $G' = ( V_{N}^{*}, V_{T}, R, A_{n} )$ とすればよいです。

補題1

任意の既約な曖昧でない文脈自由文法 $G = ( V_{N}, V_{T}, R, A_{n} )$ について、 $A_i \rightarrow^{+} A_i$ となることはない。

補題1の証明

$A_i \rightarrow^{+} A_i$ となる非終端記号があると、 $A_{n} \rightarrow^{*} x A_i y \rightarrow^{*} w$ と $A_{n} \rightarrow^{*} x A_i y \rightarrow^{+} x A_i y \rightarrow^{*} w$ と木の形が違う二通りの導出ができてしまうので、曖昧な文法になります。

定義 ( $P(G)$ )

文法 $G$ について $P(G) = \{ A_i \mid \exists x,y\, s.t.\, A_i \rightarrow^{*} x A_i y \land xy \neq \varepsilon \}$

ここで、補題1 より $G$ が既約で曖昧でないとき、 $xy = \varepsilon$ となることはないので、 $A_{i} \not \in P(G)$ のとき $A_{i}$ から $A_{i}$ を含む列を生成することはありません。

定義 (almost looping)

文法 $G = ( V_{N}, V_{T}, R, A_{n} )$ が almost looping であるとは、

$G$ は既約
$A_{1},... ,A_{n-1} \in P(G)$
任意の $w \in L(G)$ の導出において $A_{n}$ は一度しか出現しない

3 の条件が元の論文と少し違うので注意してください。

補題2

任意の既約な曖昧でない文脈自由文法 $G = ( V_{N}, V_{T}, R, A_{n} )$ について、 $L(G') = L(G)$ となる almost looping な曖昧でない文脈自由文法 $G'$ が存在する。

補題2の証明

まず、 3 が成り立っていないときは新しい開始記号 $X$ と規則 $X \rightarrow A_{n}$ を用意すれば、既約性と非曖昧性は変わらず 3 が成り立つので、最初から 3 は成り立っているものとします。

$G_{0} = G$ から非終端記号 $A_{1},... , A_{n-1}$ を 1 つずつ帰納的に処理して $G_{1},... , G_{n-1}$ と変形していきます。

処理の仕方は、ループしない非終端記号については単純に木を 1 段増やすだけなので、そのような非終端記号を文法から取り除いて、子を親に直接つなぐように生成規則を変化させるというやり方です。

具体的には以下のようになります。

(1) $A_{i} \in P(G_{i-1})$ のとき

このときは何も変化させません。

$G_{i} = G_{i-1}$ とします。

(2) $A_{i} \not \in P(G_{i-1})$ のとき

$G_{i-1} = ( V_{N,i-1}, V_{T}, R_{i-1}, A_{n} )$ とします。

$R_{i-1}$ のうち、左辺が $A_{i}$ であるものの集合を $S_{i}$ とします。

$P(G_{i-1})$ の定義と $G_{i-1}$ の非曖昧性（と補題1）より $S_{i}$ の右辺に $A_{i}$ はないはずです。

$A_{i}$ が右辺にある $G_{i-1}$ の生成規則について、 $A_{i}$ の出現をそれぞれ $S_{i}$ の右辺で置き換えたものを　 $R_{i}$ とします。

$A_{i}$ が右辺に $x$ 回出現する規則の場合は、 $|S_{i}|^x$ 個の規則に置き換わります。

そして、 $G_{i} = ( V_{N,i-1} - \{ A_{i} \}, V_{T}, R_{i}, A_{n} )$ とします。

既約性と非曖昧性は (1) の場合は文法が変化していないので成立し、 (2) の場合も、木の $A_i$ が出てくるノードについて子を親に直接つなぐようにしただけなので成立します。

また、 $j \le i$ なる非終端記号 $A_{j} \in V_{N,i}$ について $A_{j} \in P(G_{i})$ です。

これは、(i) は場合分けの定義からそのままで、(ii) も $A_i$ が無くなったので帰納法の仮定からそのまま成り立ちます。

また、生成する言語も変化しません。

以上より $G' = G_{n-1}$ とすれば目標達成です。

補題3

$L(G) = L (= \{ a^{i} b^{j} c^{k} \mid i, j, k \ge 1, i = j \lor j = k \})$ となる almost looping な文脈自由文法 $G = ( V_{N}, V_{T}, R, A_{n} )$ の開始記号でない非終端記号 $A_{i}$ は以下の 3 タイプのうちちょうど 1 つにあてはまる

$n_i, m_i \ge 0, n_i + m_i \ge 1$ が存在して $A_{i} \rightarrow^{+} a^{n_i} A_{i} a^{m_i}$ または $A_{i} \rightarrow^{+} c^{n_i} A_{i} c^{m_i}$
$n_i \ge 1$ が存在して $A_{i} \rightarrow^{+} a^{n_i} A_{i} b^{n_i}$
$n_i \ge 1$ が存在して $A_{i} \rightarrow^{+} b^{n_i} A_{i} c^{n_i}$

補題3の証明

まず各非終端記号がどのタイプかに属することを示します。

almost looping の定義から、 $A_{i} \rightarrow^{*} x A_{i} y \rightarrow^{*} w \land xy \neq \varepsilon$ となります。

ここで、 $x$ または $y$ に二種類以上の非終端記号を含むとすると、 $A_{i} \rightarrow^{*} x A_{i} y \rightarrow^{*} xx A_{i} yy$ となり、 $L$ が $a, b, c$ の順に並ばなければいけないことに反します。

よって、 $x$ と $y$ に含まれる非終端記号は高々 1 種類となり、ありえる組み合わせは次の 16 通りです

x	y	タイプ
空	空	ありえない(i)
a	空	1
b	空	ありえない(iii)
c	空	1
空	a	1
a	a	1
b	a	ありえない(ii)
c	a	ありえない(ii)
空	b	ありえない(iii)
a	b	2(v)
b	b	ありえない(iii)
c	b	ありえない(ii)
空	c	1
a	c	ありえない(iv)
b	c	3(v)
c	c	1

(i) について: $xy \neq \varepsilon$ です。

(ii) について: $L$ が $a, b, c$ の順に並ばなければいけないことに反します。

(iii) について:

$x = b^{s}, y = b^{t}$ とします。

$A_{n} \rightarrow^{*} u A_{i} v \rightarrow^{*} a^{i} b^{j} c^{k} \in L$ とします。

この真ん中の段階において、 $A_{i} \rightarrow^{*} x A_{i} y$ を $i+k+1$ 回繰り返すと、 $A_{n} \rightarrow^{*} a^{i} b^{j+(s+t)(i+k+1)} c^{k} \not \in L$ となり矛盾します。

(iv) について:

$x = a^{s}, y = c^{t}$ とします。 $A_{n} \rightarrow^{*} u A_{i} v \rightarrow^{*} a^{i} b^{j} c^{k} \in L$ とします。

この真ん中の段階において、 $A_{i} \rightarrow^{*} x A_{i} y$ を $j+1$ 回繰り返すと、 $A_{n} \rightarrow^{*} a^{i+s(j+1)} b^{j} c^{k+t(j+1)} \not \in L$ となり矛盾します。

(v) について:

$x = a^{s}, y = b^{t}, s \neq t$ とします。

$A_{n} \rightarrow^{*} u A_{i} v \rightarrow^{*} a^{i} b^{j} c^{k} \in L$ とします。この真ん中の段階において、 $A_{i} \rightarrow^{*} x A_{i} y$ を $i+j+k+1$ 回繰り返すと、 $A_{n} \rightarrow^{*} a^{i+s(i+j+k+1)} b^{j+t(i+j+k+1)} c^{k} \not \in L$ となり矛盾します。

よって $s = t = n_{i}$ です。

$x = b^{s}, y = c^{t}$ のときも同様です。

次に、どれか一つのタイプにしか属せないことを示します。

仮に、タイプ 1 とタイプ 2 に属していたとすると、

$A_{i} \rightarrow^{*} a^{s} A_{i} b^{s} \rightarrow^{*} a^{s} a^{t} A_{i} a^{u} b^{s} ( s \ge 1, t+u \ge 1 )$ となります。

$y$ は一種類の終端記号しか生成してはいけないので、 $u = 0$ または $s = 0$ です。

$s = 0$ のとき $s \ge 1$ に反します。

$u = 0$ のとき (v) の議論から $t = 0$ となり $t+u \ge 1$ に反します。

これは矛盾です。

タイプ 1 とタイプ 3 についても同様です。

仮に、タイプ 2 とタイプ 3 に属していたとすると、

$A_{i} \rightarrow^{*} a^{s} A_{i} b^{s} \rightarrow^{*} a^{s} b^{t} A_{i} c^{t} b^{s} ( s, t \ge 1 )$ となります。

$L$ が $a, b, c$ の順に並ばなければいけないことに反します。

以上より示せました。

補題4

$L(G) = L$ となる almost looping な文脈自由文法 $G = ( V_{N}, V_{T}, R, A_{n} )$ について、 $w \in L$ が $A_{n}$ と補題3のタイプ1の非終端記号からのみ生成できるとき、 $w$ に含まれる $b$ の個数は $l_{G}$ 個以下となる（ $l_{G}$ は文法 $G$ により定まる定数）