文脈自由言語の反復補題（ぶんみゃくじゆうげんごのはんぷくほだい、）は、全ての文脈自由言語が持つ属性を与える反復補題である。Bar-Hillelの補題や、uvwxy定理とも呼ばれる。その主たる用法は、ある言語が文脈自由言語でないことを証明することである。文脈自由言語の反復補題は、任意の文脈自由言語でない言語が文脈自由でないことを証明するのに使えるわけではない。場合によってはより汎用化されたオグデンの補題を使う必要がある。任意の文脈自由言語 "L" に対して，（反復長 (pumping length) と呼ばれる）ある正の整数 "p" > 0 が存在し、"L" 内の |"w"| ≥ "p" となる任意の文字列 "w" を以下のように表すことができる：このとき、文字列 "u"、"v"、"x"、"y"、"z" について |"vxy"| ≤ "p"、|"vy"| ≥ 1、そして以下が成り立つ。なお、文字列 "a" と "b" があるとき "ab" はその連結した文字列を表し、|"a"| は "a" の長さを表す。また、"a" は "a" を "i" 回反復した文字列を表す。文脈自由言語の反復補題（以下、単に反復補題と略記）は、全ての文脈自由言語が持つと保証されている属性を表している。その属性は、当該言語に含まれる長さ "p" 以上の全ての文字列について成り立つ。ここで、"p" は定数であり、反復長と呼ばれ、個々の文脈自由言語によって異なる。"s" が長さ "p" 以上の文字列とする。反復補題によれば、"s" は5つの部分文字列 formula_1 に分けられ、"vy" は空でない文字列で、"vxy" の長さは最大で "p" であり、"s" の中の "v" と "y" に相当する部分を任意の同じ回数繰り返して生成される文字列も同じ言語に含まれる（ゼロ回繰り返す場合も含まれ、その場合 "v" と "y" に相当する部分がない文字列 "uxz" となる）。このような "v" と "y" の複製を追加していくことを「反復; pumping」と呼び、そのため反復補題と呼ばれている。反復補題で言語が文脈自由でないことを証明するには、その言語に含まれる長さ "p" 以上の文字列 "s" が上述の属性を持たないことを示せばよい。つまり、反復によってその言語に含まれない文字列が生成されることを示す。文脈自由言語の反復補題は、ある言語が文脈自由言語でないことを示すのに使われる。ここでは、例として、言語 L = {abc, j>0} が文脈自由でないことを示す。

出典:wikipedia