反復補題を利用した正規言語の判別問題

問題

(1)下記の言語が正規言語ではないことを反復補題を利用して証明せよ。
$\begin{array}{r} (1) & L = (a^{n}, b^{n} | n ≧ 0) \end{array}$
(2)自由文脈文法 $G_{1} = (N_{1}, Σ_{1}, P_{1}, S_{1})$ の生成規則の集合 $P_{1}$ を与えよ。ただし、 $N_{1} = S_{1}, Σ_{1} = (a, b), S_{1}$ はそれぞれ非終端記号の集合、終端記号の集合、開始記号とする。

はじめに
直感的な証明方法
反復補題を使用した証明方法
最後に
参考文献

はじめに

オートマトンを試験範囲とする大学で、たまに出題される証明問題です。ネットで検索すると、講義資料では説明されていますが、文章として説明する場所が無いように見えました。ですので、今回紹介します。

※頻出問題としては、ある言語Lが与えられ、それに対応するオートマトンを作成する問題があります。こちらに関しては別サイトでの解説が豊富なので、今回は省略します。

標記の問題、皆様はどのような証明を考えますでしょうか。

直感的な証明方法

私が一番最初に考える証明方法は下記です。

$a^{n}, b^{n}$ であるため、aが出た回数分bが発生する必要がある。しかし、nに上限値が無いため、aが出た回数を記憶するために必要な状態が限りなく必要。

状態を規定できないため、正規言語ではない。

こちらの証明方法、ネットでもよく説明されていると思います。実際、試験という限りのある時間であれば、こちらで満点近く得点できるのではないかと考えています。

ただ、少し直感的な説明であることが否めません。数式を用いて、厳密的な証明ができないのでしょうか。

そういった時に出てくる方法が、今回紹介する「反復補題」です。上記の証明方法を背理法として説明しているに過ぎないのですが、実際に厳密的な証明を求められたときに役立つ考え方と思います。

反復補題を使用した証明方法

反復補題とは

与えられた言語Lが正規言語ならば、Lの長さがm以上の任意の系列wが存在します。

また、w=xyzと適当な文字列xyzに分割することができ、以下の条件を満たすことを言います。

任意の整数i≧0に対し、 $x y^{i} z ∊ L$
$| y | ≧ 1$
$| x y | ≦ m$

w=xyzの文字列のうち、xとzの間にあるyの個数を変化させても、その結果発生した文字列は変わらずLに属することを指しています。

今回は、背理法を用いて上記と矛盾することを証明します。

これにより、言語 $L$ は正規言語ではないことが分かります。しかし、文脈自由言語ではあります。ですので、ある生成規則 $P_{1}$ に基づいて表現できるものになります。(2)で詳しい説明をしますが、生成規則を与えるには、 $n = 0, 1, 2 \dots$ と数を上げていき(実験)、共通の生成ルールを見つけていくことが解答の定石になります。