正規言語の反復補題
この証明法は、全ての正規言語にその言語を受理する有限状態機械 (FSA) が存在するという事実を利用している。正規言語が有限であれば、十分に大きい p {\displaystyle p} に対して | w | ≥ p {\displaystyle |w|\geq p} が常に偽になるため、反復補題が真であることは自明である( | w | ≥ p {\displaystyle |w|\geq p} が偽であれば、 ( | w | ≥ p ) ⇒ ( ( ∃ x , y , z ∈ Σ ∗ ) ( w = x y z ∧ ( | y | ≥ 1 ∧ | x y | ≤ p ∧ ( ∀ i ≥ 0 ) ( x y i z ∈ L ) ) ) ) {\displaystyle (|w|\geq p)\Rightarrow ((\exists x,y,z\in \Sigma ^{*})(w=xyz\land (|y|\geq 1\land |xy|\leq p\land (\forall i\geq 0)(xy^{i}z\in L))))} という論理式全体は、 ⇒ {\displaystyle \Rightarrow } の右側の式の真偽値によらず真になる。そのため、十分に大きい p {\displaystyle p} に対して、この条件式は真となるため、正規言語が有限であれば、 ∃ p ≥ 1 {\displaystyle \exists p\geq 1} という条件を常に満たすことになる)。
反復補題を使ってある言語が正規言語でないことを示すには、背理法を用いる。ある言語 L を正規言語と仮定し、L に属する全文字列が正規言語の反復補題に従うものとする。そして、具体例によって反復補題の属性を持たない文字列があることを示し、仮定が間違っていることを導き出して、L が正規言語ではないことを示す。すなわち、文字列 w ∈ L と整数 i の組合せで反復補題に反するものを探す。
この反復補題を使えば、例えばアルファベット Σ = {a, b} を使った言語 L = {ab : n ≥ 0} が正規言語でないことを証明できる。この場合、補題に出てくる w, x, y, z, p, i をその言語に当てはめる。まず、w = ab とする。この w を w = xyz、|xy| ≤ p、|y| ≥ 1 となるよう分解し、i ≥ 0 のとき xyz が L に属するかどうかを確認する。
どのように当てはめるかということについては、3通りの方法が考えられる。
yがab (0 ≤ i ≤ n, 0 ≤ j ≤ n )であるとすると、yを繰り返すとaとbが交互に出現することになり、abというLの定義に反することになる。
正規言語が無限の場合、その言語を受理する最小 FSA が存在しなければならない。FSA の状態数は有限であるから、その個数を反復長 p とする。文字列長が p 以上の場合、反復される状態が少なくとも1つ存在する(この状態を S とする)。状態 S から S への遷移は何らかの文字列に対応する。この文字列を反復補題における y とすれば、y を含まない文字列(繰り返し部分に相当する遷移をしない場合)も、y を繰り返す文字列もFSAで受理されるため、反復補題が成り立つことがわかる。
例を見てみればより理解しやすいだろう。以下の状態遷移図は、ある FSA を示している。
この FSA は文字列 abcbcd を受理する。この文字列は状態数より多くの文字からなるので、状態を繰り返していることがわかる。この例では q1 と q2 が繰り返される状態である。文字列 abcbcd の部分文字列 bcbc は、状態 q1 から始まって状態 q1 に戻る遷移で形成されるので、この文字列部分はFSAによる繰り返しが可能であり、abcbcbcbcd のような文字列も受理される。また、その遷移のループを通らない文字列 ad も同様に受理される。反復補題に当てはめると、文字列 abcbcd は、x に a、y に bc、z に bcd が対応する。もちろん、他の当てはめ方もある(y に bcbc を対応させる)が、|xy| ≤ p を満たしていない。