ポンピング補題 - 忘れても大丈夫

有限オートマトンによって認識不可能な言語を非正規言語と呼ぶ．ここでは，ある言語が非正規言語となることを示すのによく用いられるポンピング補題について紹介する．

ポンピング補題（pumping lemma）
$A$ が正規言語であるならば，ある数 $p$ が存在して， $A$ の長さが $p$ 以上の任意の文字列 $s$ に対して，次を満たす $s$ の分割 $s = xyz$ が存在する．

　1. 任意の $i \ge 0$ について $x y^i z \in A$
　2. $0 < |y|$
　3. $|xy| \le p$

ただし， $|y|$ は文字列 $y$ の長さで， $y^i$ は $y$ を $i$ 個連結した文字列を表す（ $y^0$ は空文字列）．
また， $p$ をポンピング長（pumping length）と呼ぶ．

証明．
正規言語 $A$ を認識する有限オートマトンを $M$ として，ポンピング長 $p$ を $M$ の状態数とする．任意の文字列 $s = s_1 s_2 \cdots s_n \in A \,(n \ge p)$ を考える． $M$ が $s$ を処理するときに通過する状態の列を $r = r_1, \ldots, r_{n+1}$ とする． $n + 1 > q$ なので，鳩の巣原理より $r$ には重複する状態が少なくとも1つ存在する．そのような状態で最初に現れるものを $r_i$ , 二番目に現れるものを $r_j$ とする．このとき，下の図のように $x = s_1 \cdots s_{i - 1}, \, y = s_{i} \cdots s_{j - 1}, \, z = s_{j} \cdots s_{n}$ とすると条件1, 2, 3 を満たす分割となる．条件1はループを何回繰返しても状態 $r_j$ に戻るので受理状態となる（ $i = 0$ のときは $y^0$ は空文字列となり $xz$ となる）．条件2と条件3は $r_i, r_j$ の選び方から成り立つ．□
　　 f:id:tatanaideyo:20181229180444p:plain:w550

ポンピング補題を用いた非正規言語の証明方法

言語 $B$ が非正規言語であることを示す一般的なステップは次の3つである．
　Step 1. 背理法： $B$ は正規言語であると仮定して矛盾を導く
　Step 2. $B$ は正規言語と仮定したのでポンピング補題が成り立つようなポンピング長 $p$ が存在する
　Step 3. $B$ の文字列 $s \,(|s| \ge p)$ から条件1を満たさない文字列を見つける
　　　　（ $B$ が正規言語であることに矛盾）

例. 言語 $B = \{0^n 1^n \mid 0 \le n \}$ は非正規言語

Step 1.
　 $B$ は正規言語であると仮定して矛盾を導く．
Step 2.
　 $B$ は正規言語なのでポンピング補題が成り立つようなポンピング長 $p$ が存在する．
Step 3.
　文字列 $s = 0^p 1^p \in B$ を考えると，ポンピング補題から条件を満たす分割 $s = x y z$ が存在する．
　このとき，文字列 $x$ と $y$ は条件3の $|x y| \le p$ から文字 0 のみからなる．
　また，条件2から $y$ は空文字列ではないので長さ1以上の文字 0 のみからなる．
　ここで，文字列 $x y^{3 p} z$ を考えると明らかに文字 0 と 1 の個数が異なる．
　これは，条件1に矛盾するので， $B$ は正規言語ではない．すなわち， $B$ は非正規言語である．