翻訳と辞書
Words near each other
・ オグズ・トルコ人
・ オグズ人
・ オグズ族
・ オグズ語群
・ オグチュル島
・ オグチ・オニェウ
・ オグデン
・ オグデン (ドック型輸送揚陸艦)
・ オグデン (ユタ州)
・ オグデン (哨戒フリゲート)
オグデンの補題
・ オグデンフィップスハンデキャップ
・ オグデン・L・ミルズ
・ オグデン・フィップス
・ オグデン・ミルズ
・ オグデン・リビングストン・ミルズ
・ オグドアド
・ オグドモン
・ オグナほたかスキー場
・ オグニェン・コロマン


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

オグデンの補題 : ウィキペディア日本語版
オグデンの補題[おぐでんのほだい]
オグデンの補題: 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)
ウィキペディアで「オグデンの補題」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.