About: 文脈自由言語の反復補題

文脈自由言語の反復補題（ぶんみゃくじゆうげんごのはんぷくほだい、英: Pumping lemma for context-free languages）は、全ての文脈自由言語が持つ属性を与える反復補題である。Bar-Hillelの補題や、uvwxy定理とも呼ばれる。その主たる用法は、ある言語が文脈自由言語でないことを証明することである。 文脈自由言語の反復補題は、任意の文脈自由言語でない言語が文脈自由でないことを証明するのに使えるわけではない。場合によってはより汎用化されたオグデンの補題を使う必要がある。