反復補題のソースを表示

'''反復補題'''あるいは'''ポンピング補題'''<ref>{{Cite book |和書 |title=計算理論の基礎　&#91;原著第2版&#93; 1.オートマトンと言語 |first=Michael |last=Sipser |others=太田 和夫・田中 圭介 （監訳） |publisher=共立出版 |date=2008-05-25 |isbn=9784320122079 |origdate=2006}}</ref>（[[英語|英]]: '''Pumping lemma'''）とは、[[計算可能性理論]]において、あるクラスの[[形式言語]]に反復を施してもそのクラスに依然として属することを示すものである。ここでいう「反復」とは、その言語に含まれる十分に長い文字列が部分に分割可能で、その一部分を繰り返したさらに長い文字列も同じ言語に含まれるようにすることである。この補題の証明には、[[鳩の巣原理]]のような[[組合せ数学]]が必要とされる。

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

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

== 例 ==

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

=== 文脈自由言語の反復補題 ===
{{Main|文脈自由言語の反復補題}}
[[文脈自由言語]]は、ある固定された[[文脈自由文法]]によって生成される語の集合として定義される。もしくは、(ある1つの) [[プッシュダウン・オートマトン]]で受理可能な語すべての集合とも定義される。文脈自由言語の反復補題とは、以下の内容を指す。
{{Math theorem|反復補題|任意の文脈自由言語 {{Mvar|L}} に対して、ある1以上の値 {{Mvar|r}} が存在して、長さ {{Mvar|r}} 以上の任意の語 {{Math|''w'' ∊ ''L''}} は以下の条件を満たす部分文字列 {{Math|''u'', ''v'', ''x'', ''y'', ''z''}} によって {{Math|''w'' {{=}} ''uvxyz''}} と分割できる。
# <math>\vert vxy\vert\leqq r</math> … {{Mvar|vxy}} は長さ {{Mvar|r}} 以下である。
# <math>\vert v\vert+\vert y\vert\geqq 1</math> … {{Mvar|v}} と {{Mvar|y}} の少なくとも一方は空文字列でない。
# <math>uv^ixy^iz \in L\;\;(i\geq 0)</math> … {{Mvar|v}} と {{Mvar|y}} を同じ回数繰り返した文字列 {{Mvar|uvv…vxyy…yz}} はすべて {{Mvar|L}} の語である。|note=ポンピング補題}}

== 脚注 ==
{{脚注ヘルプ}}
{{Reflist}}

== 参考文献 ==
* {{cite book|author = Michael Sipser | date = 1997年 | title = Introduction to the Theory of Computation | publisher = PWS Publishing | id = ISBN 0-534-94728-X}} Section 1.4: Nonregular Languages, pp.77&ndash;83. Section 2.3: Non-context-free Languages, pp.115&ndash;119.

{{DEFAULTSORT:はんふくほたい}}
[[Category:形式言語]]
[[Category:補題]]
[[Category:数学に関する記事]]