ポンピング補題の練習

B1-2向け.

DFA用のポンピング補題は割と簡単に証明が出来ます. 状態数以上の文字列をDFAに入力として与えたときには, 鳩ノ巣原理より, 必ずどこかの状態を2回通っているということが直観です.
反復補題とも言われる様子 (→正規言語の反復補題 - Wikipedia)

ポンピング補題だけ見てもあまり有り難味は感じられませんが, ある言語が正規でないことを証明するときには強力な武器になります.
例として, $L=\{0^n1^n|n\in \mathbb{N}\cap\{0\}\}$ が正規でないことを示してみましょう.

証明

背理法で証明する. Lが正規言語であると仮定する. ポンピング補題よりある定数pが存在して以下が成立する:
任意のs∈Lについて, |s|≧pならばs=xyzと書け,

任意のi≧0について $xy^iz\in L$
|y|＞0
|xy|≦p

が成立.

今, sとして $0^p1^p$ を取る. これはLに含まれている.
条件3よりxyの長さはp以下である. また, 条件2よりyの長さは1以上である.
よって, ある整数kとlが存在して, x=0^k, y=0^l, l≧1, k≧0, k+l≦pとなっている筈である.
このとき, $z=0^{p-k-l}1^p$ となっている.
ここで, 条件1の式でi=0とおけば, $xz=0^{p-l}1^p$ がLに含まれるはずである. しかし, Lの定義より, xzはLに含まれない (l≧1より, 0と1の個数が異なる). よって矛盾.