反復補題
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/10/20 22:52 UTC 版)
反復補題あるいはポンピング補題[1]（英: Pumping lemma）とは、計算可能性理論において、あるクラスの形式言語に反復を施してもそのクラスに依然として属することを示すものである。ここでいう「反復」とは、その言語に含まれる十分に長い文字列が部分に分割可能で、その一部分を繰り返したさらに長い文字列も同じ言語に含まれるようにすることである。この補題の証明には、鳩の巣原理のような組合せ数学が必要とされる。
- ^ Sipser, Michael『計算理論の基礎 [原著第2版] 1.オートマトンと言語』太田 和夫・田中 圭介 （監訳）、共立出版、2008年5月25日（原著2006年）。ISBN 9784320122079。
[続きの解説]
- 反復補題のページへのリンク
