正則言語のPumping Lemma
・L⊆Σ*を正則言語とする。このとき、ある定数N>=1が存在して、Lに属する長さがN以上の任意の記号列xに対して、xの分解x=uvwで次の条件を満たすものがある。
1. 1<=|v|
(証明の要点は、状態数Nに対してそれより長い記号列を投げたら状態の繰り返しが起きるはずなので、その状態の始点と終点に対応する記号を切って繰り返し対象にすればOKという点。これが正則でない言語でアウトなのは、繰り返しが作れないから:だいたい繰り返しを0回や無限回にした記号列が言語から外れてしまう。正則でないことは背理法でこれを使って証明する)