正規言語の反復補題
次に、|xy|=p かつ |z|=p としたとき、xy は w の前半、すなわち p 個の a に対応する。|y| ≥ 1 なので、y は1個以上の a で構成される。すると、xyz は a の個数と b の個数が違うことになり、L の定義に反する(i ≠ 1 について常に矛盾が生じる)。この場合、矛盾が導かれたので、反復補題が成り立たないことがわかる。
もうひとつのパターンは、|xy|=p=|w| かつ |z|=0 の場合、つまりx=a、y=b, z= ε {\displaystyle \epsilon } の場合であるが、これも同様に、xyz は a の個数と b の個数が違うことになり、L の定義に反する。従って、Lに属する文字列をどのように分割しても、反復補題から矛盾が導かれ、L が正規言語であるという仮定に誤りがあることになる。従って、L が正規言語でないことが証明される。
括弧が正しく対応している言語('(' と ')' が同じ個数出現し、最初が '(' で最後が ')' となる言語)も同様の考え方で正規言語でないことが証明できる。ある p について、左括弧が先頭から p 個以上続く文字列では、y には左括弧しか含まれない。従って y を反復すると、左括弧だけが多い文字列となって、定義に反することになる。