翻訳と辞書 Words near each other ・ 反復発生 ・ 反復発生説 ・ 反復発芽 ・ 反復的開発 ・ 反復積分 ・ 反復積分に関するコーシーの公式 ・ 反復突然変異 ・ 反復符号 ・ 反復経頭蓋磁気刺激 ・ 反復興奮 ・ 反復補題 ・ 反復親 ・ 反復解法 ・ 反復計算 ・ 反復記号 ・ 反復試験区 ・ 反復説 ・ 反復調律、反復リズム(二段脈など)、同期(周期)性不整脈 ・ 反復過多損傷 ・ 反復選択 Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク 反復補題 ： ウィキペディア日本語版 反復補題[はんぷくほだい] 反復補題（英: Pumping lemma）とは、計算可能性理論において、あるクラスの形式言語に反復を施してもそのクラスに依然として属することを示すものである。ここでいう「反復」とは、その言語に含まれる十分に長い文字列が部分に分割可能で、その一部分を繰り返したさらに長い文字列も同じ言語に含まれるようにすることである。この補題の証明には、鳩の巣原理のような組合せ数学が必要とされる。 反復補題の重要な具体例として、正規言語の反復補題と文脈自由言語の反復補題がある。文脈自由言語の反復補題の一種として、オグデンの補題もある。 これらの補題は、ある言語が特定の言語クラスに属さないことを示すのに使われる。しかし逆に、反復補題を満たすことは必要条件ではあっても十分条件ではないので、ある言語があるクラスに属することを示すのには使えない。 == 参考文献 == * Section 1.4: Nonregular Languages, pp.77–83. Section 2.3: Non-context-free Languages, pp.115–119. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「反復補題」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.