翻訳と辞書
Words near each other
・ Updates (ベイエフエム)
・ Upside Down (電気グルーヴの曲)
・ Uptown Girl (ウエストライフの曲)
・ Ura E 〜Complete B side Melodies〜
・ Ura-ユリ
・ Uraayu - 裏歩
・ Us (ピーター・ガブリエルのアルバム)
・ Us 〜空と大地の間で〜
・ Usbメモリー
・ Utada Hikaru in BudoKan 2004 ヒカルの5
Uvwxy定理
・ UÇK
・ UÇPMB
・ UÇÇ
・ U★STONE
・ Uインター
・ Uウムラウト
・ Uクルージュ
・ Uグラーヴ
・ Uコン


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

Uvwxy定理 : ミニ英和和英辞書
Uvwxy定理[り]
=====================================
〔語彙分解〕的な部分一致の検索結果は以下の通りです。

定理 : [ていり]
 【名詞】 1. theorem 2. proposition
: [り]
 【名詞】 1. reason 

Uvwxy定理 ( リダイレクト:文脈自由言語の反復補題 ) : ウィキペディア日本語版
文脈自由言語の反復補題[ぶんみゃくじゆうげんごのはんぷくほだい]
文脈自由言語の反復補題(ぶんみゃくじゆうげんごのはんぷくほだい、)は、全ての文脈自由言語が持つ属性を与える反復補題である。Bar-Hillelの補題や、uvwxy定理とも呼ばれる。その主たる用法は、ある言語が文脈自由言語でないことを証明することである。
文脈自由言語の反復補題は、任意の文脈自由言語でない言語が文脈自由でないことを証明するのに使えるわけではない。場合によってはより汎用化されたオグデンの補題を使う必要がある。
== 形式的定義 ==
言語 ''L'' が有限で文脈自由であるとき、ある正の整数 ''p'' > 0 が存在し、''L'' 内の任意の文字列 ''w'' について |''w''| ≥ ''p'' が成り立つことを以下のように記述する(ここで、''p'' は反復長 (pumping length) である)。
:''w'' = ''uvxyz''
このとき、文字列 ''u''、''v''、''x''、''y''、''z'' について |''vxy''| ≤ ''p''、|''vy''| ≥ 1、そして以下が成り立つ。
: 全ての0以上の整数 ''i'' ≥ 0 について ''uv ixy iz'' が ''L'' に含まれる。
なお、文字列 ''a'' と ''b'' があるとき ''ab'' はその連結した文字列を表し、|''a''| は ''a'' の長さを表す。また、''ai'' は ''a'' を ''i'' 回反復した文字列を表す。

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「文脈自由言語の反復補題」の詳細全文を読む

英語版ウィキペディアに対照対訳語「 Pumping lemma for context-free languages 」があります。




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

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