|
オグデンの補題（英: Ogden's lemma）とは、形式言語の理論において、文脈自由言語の反復補題の柔軟性を拡張したものである。 具体的には次の通りである。言語 ''L'' が文脈自由であるとき、ある正の数 ''p'' が存在し（''p'' は反復長とは限らない）、''L'' における ''p'' 以上の長さの任意の文字列 ''w'' について、''w'' 上の ''p'' 個以上の位置（文字）をマークする全ての組合せを考える。''w'' は次のように表される。 :''w'' = ''uvxyz'' ここで、''u'', ''v'', ''x'', ''y'', ''z'' という文字列について、''vy'' が少なくとも1つのマークされた位置を含み（すなわち ''|vy|'' > 0）、''vxy'' には最大でも ''p'' 個のマークされた位置があるとする。すると :全ての ''i'' ≥ 0 について ''uvixyiz'' は ''L'' に含まれる。 オグデンの補題は、文脈自由言語の反復補題では示せない場合でも、特定の言語が文脈自由でないことを示すことができる。例えば、言語 がそのような言語である。 全位置（文字）がマークされるとき、この補題は文脈自由言語の反復補題と等価になる。 == 関連項目 == * 反復補題 * 文脈自由言語の反復補題 * 正規言語の反復補題 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「オグデンの補題」の詳細全文を読む スポンサード リンク
|