反復補題
反復補題あるいはポンピング補題[1]（英: Pumping lemma）とは、計算可能性理論において、あるクラスの形式言語に反復を施してもそのクラスに依然として属することを示すものである。ここでいう「反復」とは、その言語に含まれる十分に長い文字列が部分に分割可能で、その一部分を繰り返したさらに長い文字列も同じ言語に含まれるようにすることである。この補題の証明には、鳩の巣原理のような組合せ数学が必要とされる。
反復補題の重要な具体例として、正規言語の反復補題と文脈自由言語の反復補題がある。文脈自由言語の反復補題の一種として、オグデンの補題もある。
これらの補題は、ある言語が特定の言語クラスに属さないことを示すのに使われる。しかし逆に、反復補題を満たすことは必要条件ではあっても十分条件ではないので、ある言語があるクラスに属することを示すのには使えない。
例
正規言語の反復補題
テンプレート:Main 正規言語は、ある１つの決定性有限オートマトンで受理可能な語すべての集合 テンプレート:Mvar として定義される。同値な定義としては、ある正規表現で記述される語の集合などが存在する。正規言語の反復補題（ポンピング補題）とは、以下の内容を指す。 テンプレート:Math theorem
文脈自由言語の反復補題
テンプレート:Main 文脈自由言語は、ある固定された文脈自由文法によって生成される語の集合として定義される。もしくは、(ある1つの) プッシュダウン・オートマトンで受理可能な語すべての集合とも定義される。文脈自由言語の反復補題とは、以下の内容を指す。 テンプレート:Math theorem
脚注
参考文献
- テンプレート:Cite book Section 1.4: Nonregular Languages, pp.77–83. Section 2.3: Non-context-free Languages, pp.115–119.