正則言語のPumping Lemma

正則言語のPumping Lemma
・L⊆Σ*を正則言語とする。このとき、ある定数N>=1が存在して、Lに属する長さがN以上の任意の記号列xに対して、xの分解x=uvwで次の条件を満たすものがある。
　1. 1<=|v|=NとなるLの記号列xについて、xはMによって受理されるので、xのMによる受理計算が存在する。Mの状態数はNであり、xの長さn>=Nであるので、受理計算p0~pnには同じ状態が少なくとも2つ現れている。この状態をpi=pj(i=0に対してpi=pjだからi~jのm回の繰り返しは受理される（厳密には受理計算の流れを書いたほうがいい）。
（証明の要点は、状態数Nに対してそれより長い記号列を投げたら状態の繰り返しが起きるはずなので、その状態の始点と終点に対応する記号を切って繰り返し対象にすればOKという点。これが正則でない言語でアウトなのは、繰り返しが作れないから：だいたい繰り返しを0回や無限回にした記号列が言語から外れてしまう。正則でないことは背理法でこれを使って証明する）