これは先の証明の日本語訳である。ここでは長さが素数の文字列で構成された言語は正規言語でないをことを示す。 この証明には正規言語の反復補題の対偶を用いる。 全ての正規言語はこの補題を満たすので、この補題が満たされないことを示せば、前記の命題を証明することができる。

対偶法による証明

対偶が真、つまり前記の言語が正規言語、だと仮定する。 すると、この言語を理解する有限オートマトンが存在する。 これを仮にMと呼ぶ。 さらに、この言語について反復補題が成立する。 即ち、$$L(M)$$に属する任意の文字列wについて長さがそれ以上であれば 下記の条件を満たす$$w=xyz$$に分解することができる反復数p(自然数)が存在する。

1. $$|y|>0$$
2. $$|xy|\le p$$
3. $$\mathrm{\forall }i\in {\mathbb{Z}}_{\ge 0},x{y}^{i}z\in L(M)$$

ここで、素数は無限に存在するので、pより大きい最小の素数をkとすれば、 $$|w|=k$$を満たす$$w\in L(M)$$が存在するはずである。 $$w\in L(M)$$ で $$|w|>p$$なので、補題の条件を満たした$$w=xyz$$に分解することができる。

ここで新たな文字列vを$$v=x{y}^{k+1}z$$と置く。 上記の条件3により$$v\in L(M)$$なので、vの文字列長は素数である。 しかし$$|v|=|x{y}^{k+1}z|=|xyz|+|y^k|=k+|y|k=k(1+|y|)$$。 明らかに$$k\mid k(1+|y|)$$であり、$$k>1$$なので、$$|v|$$は素数ではない。 この矛盾は仮定が偽であったことを示すので、反復補題により前記の言語は正規でない。 Q.E.D.

思いのほか、日本語での証明は困難・・・