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

流れは大体 [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} 
ightarrow alpha_{1}... alpha_{k} のように表します。

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

生成規則を 1 回以上適用して新しい列を生成することを  A_{i} 
ightarrow^{+} 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} 
ightarrow^{*} x A_i y ) land ( exists w, s.t., A_i 
ightarrow^{*} w ) } とすると、 G' = ( V_{N}^{*}, V_{T}, R, A_{n} ) とすればよいです。

補題1

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

補題1の証明

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

定義 ( P(G))

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

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

定義 (almost looping)

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

  1.  G は既約
  2.  A_{1},... ,A_{n-1} in P(G)
  3. 任意の  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 
ightarrow 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} 
ot 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 つにあてはまる

  1.  n_i, m_i ge 0, n_i + m_i ge 1 が存在して  A_{i} 
ightarrow^{+} a^{n_i} A_{i} a^{m_i} または  A_{i} 
ightarrow^{+} c^{n_i} A_{i} c^{m_i}
  2.  n_i ge 1 が存在して  A_{i} 
ightarrow^{+} a^{n_i} A_{i} b^{n_i}
  3.  n_i ge 1 が存在して  A_{i} 
ightarrow^{+} b^{n_i} A_{i} c^{n_i}
補題3の証明

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

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

ここで、 x または  y に二種類以上の非終端記号を含むとすると、 A_{i} 
ightarrow^{*} x A_{i} y 
ightarrow^{*} 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 
eq varepsilon です。

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

(iii) について:

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

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

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

(iv) について:

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

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

(v) について:

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

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

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

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

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

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

 A_{i} 
ightarrow^{*} a^{s} A_{i} b^{s} 
ightarrow^{*} 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} 
ightarrow^{*} a^{s} A_{i} b^{s} 
ightarrow^{*} 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 により定まる定数)

補題4の証明

 w の導出木を考えます。

almost looping なので、 A_{n} は一度しか現れません。

タイプ1の非終端記号  A_{i} を表す頂点  v の子孫に  A_{i} を表す頂点  u が現れるとき、 v の部分木を  u の部分木で置き換えても  b の個数は変わりません。

これを繰り返して、子孫に同じ非終端器号が現れない木  T を作り、これが表す終端記号列を  w' とします。

根からのパスに同じ非終端記号が現れないので  T の深さは  n+1 以下です。

 R の生成規則の右辺に現れる記号の最大数を  r とします。

すると、 |w'| le r^{n} なので、 w に含まれる  b の個数も  r^{n} 個以下です。

よって、 l_{G} = r^{n} とすれば良いことが分かります。

 L が本質的に曖昧であることの証明

背理法により証明します。

 L を生成する曖昧でない文法  G が存在したと仮定します。

補題0 より、 L を生成する既約で曖昧でない文法  G' が存在します。

補題2 より、 L を生成する almost looping な曖昧でない文法  G^{*} が存在します。

補題3 のタイプ 2 とタイプ 3 について  n_i を全て掛けあわせたものを  K とします。

補題4 の  l_{G} について、 p > l_{G^{*}} となる  K の倍数  p をとります。

 w_{1} = a^{p} b^{p} c^{2p} in L を考えます。

 p > l_G^{*} なので、補題 4 より、タイプ 2 かタイプ 3 の非終端記号が  w の導出の過程で現れます。

仮にタイプ 3 の非終端記号  A_{i} w の導出で出現したとすると、

 A_{n} 
ightarrow^{*} u A_{i} v 
ightarrow^{*} a^{p} b^{p} c^{2p}

 A_{n} 
ightarrow^{*} u A_{i} v 
ightarrow^{*} u b^{p} A_{i} c^{p} v 
ightarrow^{*} a^{p} b^{2p} c^{3p} 
ot in L

となり矛盾するので、 w の導出にはタイプ 3 の非終端記号は含まれていません。

よって、タイプ 2 の終端記号  A_{j} w の導出の過程で出現します。

 A_{n} 
ightarrow^{*} u A_{j} v 
ightarrow^{*} a^{p} b^{p} c^{2p}

 A_{n} 
ightarrow^{*} u A_{j} v 
ightarrow^{*} u a^{p} A_{j} b^{p} v 
ightarrow^{*} a^{2p} b^{2p} c^{2p}

この導出の過程でタイプ 2 の非終端記号が出現し、タイプ 3 の非終端記号は出現しません。

同様に  w_{2} = a^{2p} b^{p} c^{p} in L を考えると、タイプ 3 の非終端記号が出現し、タイプ 2 の非終端記号は出現しないような  a^{2p} b^{2p} c^{2p} の導出があります。

これは  a^{2p} b^{2p} c^{2p} の異なる導出木があることを意味し、 G^{*} が曖昧な文法となり、矛盾が生じます。

よって、 L は本質的に曖昧です。

最後に

もしもっと簡単に証明できるのならぜひ教えてください。

何か間違いや質問などがあればお願いします。

最後まで読んでいただきありがとうございました。

参考文献

[1] Herman A. Maurer. (1969). A Direct Proof of the Inherent Ambiguity of a Simple Context-Free Language.

[2] Michael Sipser. (2008). 計算理論の基礎 [原著第2版] 1.オートマトンと言語. (訳書)