文脈自由言語の反復補題
文脈自由言語の反復補題(以下、単に反復補題と略記)は、全ての文脈自由言語が持つと保証されている属性を表している。その属性は、当該言語に含まれる長さ p 以上の全ての文字列について成り立つ。ここで、p は定数であり、反復長と呼ばれ、個々の文脈自由言語によって異なる。s が長さ p 以上の文字列とする。反復補題によれば、s は5つの部分文字列 s = u v x y z {\displaystyle s=uvxyz} に分けられ、vy は空でない文字列で、vxy の長さは最大で p であり、s の中の v と y に相当する部分を任意の同じ回数繰り返して生成される文字列も同じ言語に含まれる(ゼロ回繰り返す場合も含まれ、その場合 v と y に相当する部分がない文字列 uxz となる)。このような v と y の複製を追加していくことを「反復; pumping」と呼び、そのため反復補題と呼ばれている。
反復補題で言語が文脈自由でないことを証明するには、その言語に含まれる長さ p 以上の文字列 s が上述の属性を持たないことを示せばよい。つまり、反復によってその言語に含まれない文字列が生成されることを示す。
文脈自由言語の反復補題(ぶんみゃくじゆうげんごのはんぷくほだい、英: Pumping lemma for context-free languages)は、全ての文脈自由言語が持つ属性を与える反復補題である。Bar-Hillelの補題や、uvwxy定理とも呼ばれる。その主たる用法は、ある言語が文脈自由言語でないことを証明することである。
文脈自由言語の反復補題は、任意の文脈自由言語でない言語が文脈自由でないことを証明するのに使えるわけではない。場合によってはより汎用化されたオグデンの補題を使う必要がある。