ポンピング補題
定理1. ポンピング補題
\begin{align} &\forall L\in\mathcal{REG},\ \exists p\in\mathbb{N}, \ \forall w(|w|\geq p)\in L,\ \exists x,y,z\in T^*\\[4pt] &\left[w=xyz\ \land\ |xy|\leq p\ \land\ |y|\geq 1\ \land \ \forall i\in\mathbb{Z}^+(xy^iz\in L)\right] \end{align}ただし \(\mathcal{REG}\) は正規言語全体の集合を, \(T\) は \(L\) の終端記号のアルファベットを表す. またここでの \(p\) をポンピング長と呼ぶ。
定理2. ポンピング補題の応用
\[ \{ 0^n1^n|n\in\mathbb{Z}^+\}\notin\mathcal{REG} \]証明
方針
正規言語において十分に長い語は、 有限オートマトンによって受理されるときに、 同じ内部状態を複数回通過しなければならない。 ↓ その語を重複した内部状態の位置で分割すれば、最初の部分＋迂回部分＋最後の部分に分けられるのでは！？
定理1の証明
任意の \(L\in\mathcal{REG}\) を考える. 正規言語の並列定義に関する定理 より \(L\) を受理するDFT \(M\) が存在する.
ここで \(p=|Q|\) (\(Q\) は \(M\) の内部状態集合) とすれば, 任意の \(w\ (|w|\geq p)\in L\) について, \(M\) が \(w\) を受理するために通過する状態列 \(r\) の長さは \(|w|+1\) である.
この状態列 \(r=(r_1,r_2,...,r_{|w|+1})\) について
\[ |r|=|w|+1\ge p+1=|Q|+1 \]より, \(r_1,r_2,...,r_{p+1}\in Q\) に含まれる状態の中には重複する状態の組が存在する.
その組のひとつを \(r_i,r_j(1\le i\lt j\le p+1)\) とすれば, \(w\) は
(1) \(r_1\) から \(r_i\) に到達するまでに受け取られた部分列 \(x(|x|=i-1)\) (2) \(r_i\) から \(r_j\) に到達するまでに受け取られた部分列 \(y(|y|=j-i)\) (3) \(r_j\) から \(r_{|z|+1}\) に到達するまでに受け取られた部分列 \(z(|z|=|w|-j+1)\)
に分割される. このとき
\begin{align} &|xy|=j-1\le p\\ &|y|=j-i\ge 1 \end{align}また, \(r_i\) から \(r_j\) までの経路を何度繰り返しても必ず終状態に到達するから
\[ \forall i\in\mathbb{Z}^+\ (xy^iz\in L) \]
(証明終)
定理2の証明
背理法によって示す.
\(L\triangleq\{0^n1^n\ |\ n\in\mathbb{Z}^+\}\) について \(L\in\mathcal{REG}\) と仮定すると ポンピング補題を満足するポンピング長 \(p\in\mathbb{N}\) が存在する.
このとき \(w\triangleq0^p1^p\in L\) について \(|xy|\le p\) より \(x,y\) はいずれも \(0\) のみからなる.
ここで \(m\triangleq |x|(\ge 0), \ n\triangleq |y|(\ge 1)\) とおけば
\[ x=0^m,\ y=0^n,\ z=0^{p-m-n}1^p \]このとき \(xy^2z=0^{p+n}1^p\notin L\) より \(p\) はポンピング補題を満足しない.
よって矛盾が導かれ, \(L\notin\mathcal{REG}\) が示された.
(証明終)