文脈自由言語の反復補題
任意の文脈自由言語 L に対して,(反復長 (pumping length) と呼ばれる)ある正の整数 p > 0 が存在し、L 内の |w| ≥ p となる任意の文字列 w を以下のように表すことができる:
w = uvxyz
このとき、文字列 u、v、x、y、z について |vxy| ≤ p、|vy| ≥ 1、そして以下が成り立つ。
全ての0以上の整数 i ≥ 0 について uvxyz が L に含まれる。
なお、文字列 a と b があるとき ab はその連結した文字列を表し、|a| は a の長さを表す。また、a は a を i 回反復した文字列を表す。