反復補題
正規言語は、ある1つの決定性有限オートマトンで受理可能な語すべての集合 L として定義される。同値な定義としては、ある正規表現で記述される語の集合などが存在する。正規言語の反復補題(ポンピング補題)とは、以下の内容を指す。
反復補題 (ポンピング補題) ― 任意の正規言語 L に対して、ある1以上の値 r が存在して、長さ r 以上の任意の語 w ∊ L は以下の条件を満たす部分文字列 x, y, z によって w = xyz と分割できる。
| x y | ≦ r {\displaystyle \vert xy\vert \leqq r} ... xy は長さ r 以下である。
| y | ≧ 1 {\displaystyle \vert y\vert \geqq 1} ... y は空文字列でない。
x y i z ∈ L ( i ≥ 0 ) {\displaystyle xy^{i}z\in L\;\;(i\geq 0)} ... y を何度か繰り返した文字列 xyy...yz はすべて L の語である。