文脈自由言語の反復補題
文脈自由言語の反復補題は、ある言語が文脈自由言語でないことを示すのに使われる。ここでは、例として、言語 L = {abc, j>0} が文脈自由でないことを示す。
L が文脈自由であると仮定する 条件: | vxy | ≤ p。つまり、中央部分は長すぎない。 vy ≠ ε(空の文字列)。v と y は「反復」対象なので、この条件は反復すべき文字列の少なくとも一方が空文字列でないことを意味する。 全ての i ≥ 0 について、uvxyz が L に含まれる。すなわち、2つの文字列 v と y は 0 回を含む任意の回数反復され、それによって生成された文字列も L に含まれる。
w ∈ L かつ | w | > p であるような文字列 w について、w = uvxyz と表され、| vxy | ≤ p が成り立つとする。
ここで、p より大きい値 j を選ぶ。
そして、文字列 vxy が文字列 abc に含まれるとした場合、a の右端の文字と c の左端の文字の間には j 個の文字があるため、vxy には最大でも2種類の文字しか含まれないことになる。