正規言語の反復補題
正規言語の反復補題(英: pumping lemma for regular languages)とは、全ての正規言語が持つ属性を与える補題である。反復補題一般の具体例の一つである。その主たる用法は、ある言語が正規言語でないことを証明することである。
この反復補題は1961年に Y. Bar-Hillel、M. Perles、E. Shamir によって最初に示された。
さらに、反復補題は xy の長さが最大でも p となるような s の分割があることを保証している。
反復補題は、ある言語が正規言語ではないことを証明するのに使われる(補題と呼ばれるのはそのためである)。その場合、反復補題に示される属性をその言語に属する文字列が持たないことを示せばよい。
正規言語が有限の場合、つまりその正規言語に含まれる文字列の長さに上限がある場合、 p {\displaystyle p} をその正規言語に含まれる最大の文字列長より大きいと仮定すると、反復補題の形式的表現の論理式は常に真となる。つまり反復補題が意味するところは、正規言語は有限か、無限であれば、任意の文字列の中間に表れる文字列に対する反復(任意回数の繰り返し)を、その正規言語が許容するということであり、いずれの場合でもないものは、正規言語ではないということである。
L {\displaystyle L} を正規言語とすると、 L {\displaystyle L} のみに依存する次のような反復長 p ≥ 1 {\displaystyle p\geq 1} が存在する。 L {\displaystyle L} に属する長さ p {\displaystyle p} 以上の任意の文字列 w {\displaystyle w} は w = x y z {\displaystyle w=xyz} と書ける(つまり、 w {\displaystyle w} は3つの部分文字列に分けられる)。ここで、 x {\displaystyle x} 、 y {\displaystyle y} 、 z {\displaystyle z} は次の条件を満たす。
| y | ≥ 1 {\displaystyle |y|\geq 1}
| x y | ≤ p {\displaystyle |xy|\leq p}
全ての i ≥ 0 {\displaystyle i\geq 0} について、 x y i z ∈ L {\displaystyle xy^{i}z\in L}
y は反復される部分文字列(0回を含む任意の回数繰り返され、結果として生成される文字列も L に属する)。|y| は文字列 y の長さを意味し、(1)の条件は y が少なくとも長さを持つ空でない文字列であることを意味している。