反復補題

反復補題あるいはポンピング補題（英: Pumping lemma）とは、計算可能性理論において、あるクラスの形式言語に反復を施してもそのクラスに依然として属することを示すものである。ここでいう「反復」とは、その言語に含まれる十分に長い文字列が部分に分割可能で、その一部分を繰り返したさらに長い文字列も同じ言語に含まれるようにすることである。この補題の証明には、鳩の巣原理のような組合せ数学が必要とされる。

反復補題の重要な具体例として、正規言語の反復補題と文脈自由言語の反復補題がある。文脈自由言語の反復補題の一種として、オグデンの補題もある。

これらの補題は、ある言語が特定の言語クラスに属さないことを示すのに使われる。しかし逆に、反復補題を満たすことは必要条件ではあっても十分条件ではないので、ある言語があるクラスに属することを示すのには使えない。

例

正規言語の反復補題

詳細は「正規言語の反復補題」を参照

正規言語は、ある１つの決定性有限オートマトンで受理可能な語すべての集合 L として定義される。同値な定義としては、ある正規表現で記述される語の集合などが存在する。正規言語の反復補題（ポンピング補題）とは、以下の内容を指す。

反復補題 (ポンピング補題) ― 任意の正規言語 L に対して、ある1以上の値 r が存在して、長さ r 以上の任意の語 w ∊ L は以下の条件を満たす部分文字列 x, y, z によって w = xyz と分割できる。

1. $\vert xy\vert \leqq r$ … xy は長さ r 以下である。
2. $\vert y\vert \geqq 1$ … y は空文字列でない。
3. $xy^{i}z\in L\;\;(i\geq 0)$ … y を何度か繰り返した文字列 xyy...yz はすべて L の語である。

文脈自由言語の反復補題

詳細は「文脈自由言語の反復補題」を参照

文脈自由言語は、ある固定された文脈自由文法によって生成される語の集合として定義される。もしくは、(ある1つの) プッシュダウン・オートマトンで受理可能な語すべての集合とも定義される。文脈自由言語の反復補題とは、以下の内容を指す。

反復補題 (ポンピング補題) ― 任意の文脈自由言語 L に対して、ある1以上の値 r が存在して、長さ r 以上の任意の語 w ∊ L は以下の条件を満たす部分文字列 u, v, x, y, z によって w = uvxyz と分割できる。

1. $\vert vxy\vert \leqq r$ … vxy は長さ r 以下である。
2. $\vert v\vert +\vert y\vert \geqq 1$ … v と y の少なくとも一方は空文字列でない。
3. $uv^{i}xy^{i}z\in L\;\;(i\geq 0)$ … v と y を同じ回数繰り返した文字列 uvv…vxyy…yz はすべて L の語である。

参考文献

• Michael Sipser (1997年). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X  Section 1.4: Nonregular Languages, pp.77–83. Section 2.3: Non-context-free Languages, pp.115–119.