|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 反 ： [はん, たん] 1. (n,vs,n-pref) anti- 2. opposite 3. antithesis 4. antagonism ・ 反復 ： [はんぷく] 1. (n,vs) repetition 2. reverse ・ 補題 ： [ほだい] (n) subtitle ・ 題 ： [だい] 1. (n,vs) title 2. subject 3. theme 4. topic
反復補題（英: Pumping lemma）とは、計算可能性理論において、あるクラスの形式言語に反復を施してもそのクラスに依然として属することを示すものである。ここでいう「反復」とは、その言語に含まれる十分に長い文字列が部分に分割可能で、その一部分を繰り返したさらに長い文字列も同じ言語に含まれるようにすることである。この補題の証明には、鳩の巣原理のような組合せ数学が必要とされる。 反復補題の重要な具体例として、正規言語の反復補題と文脈自由言語の反復補題がある。文脈自由言語の反復補題の一種として、オグデンの補題もある。 これらの補題は、ある言語が特定の言語クラスに属さないことを示すのに使われる。しかし逆に、反復補題を満たすことは必要条件ではあっても十分条件ではないので、ある言語があるクラスに属することを示すのには使えない。 == 参考文献 == * Section 1.4: Nonregular Languages, pp.77–83. Section 2.3: Non-context-free Languages, pp.115–119. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「反復補題」の詳細全文を読む スポンサード リンク
|