正規言語の反復補題
正規言語の反復補題(以下、単に反復補題と略記)は、全ての正規言語が持つと保証されている属性を表している。より正確に言えば、正規言語に属する文字列の持つ属性を表している。ここで扱う正規言語の文字列は長さ p 以上(p は定数。形式的定義での p と同じ)で、これを反復長(pumping length)と呼ぶ。反復長は個々の正規言語によって異なる。s が長さ p 以上のある文字列で、正規言語 L に含まれるものとする。反復補題によれば、何らかの方法で s を3つに分割して s = x y z {\displaystyle s=xyz} としたとき、その(空ではない)中央部分 yを(0回を含む)任意回数繰り返した文字列も L に含まれる。このように文字列の一部の複製を追加していくことを「反復; pumping」と呼び、そのため反復補題と呼ばれている。