文脈自由言語の反復補題とは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > 文脈自由言語の反復補題の意味・解説 

文脈自由言語の反復補題

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2025/01/10 02:12 UTC 版)

文脈自由言語の反復補題(ぶんみゃくじゆうげんごのはんぷくほだい、: Pumping lemma for context-free languages)は、全ての文脈自由言語が持つ属性を与える反復補題である。Bar-Hillelの補題や、uvwxy定理とも呼ばれる。その主たる用法は、ある言語が文脈自由言語でないことを証明することである。

文脈自由言語の反復補題は、任意の文脈自由言語でない言語が文脈自由でないことを証明するのに使えるわけではない。場合によってはより汎用化されたオグデンの補題を使う必要がある。

形式的定義

任意の文脈自由言語 L に対して,(反復長 (pumping length) と呼ばれる)ある正の整数 p > 0 が存在し、L 内の |w| ≥ p となる任意の文字列 w を以下のように表すことができる:

w = uvxyz

このとき、文字列 uvxyz について |vxy| ≤ p、|vy| ≥ 1、そして以下が成り立つ。

全ての0以上の整数 i ≥ 0 について uv ixy izL に含まれる。

なお、文字列 ab があるとき ab はその連結した文字列を表し、|a| は a の長さを表す。また、aiai 回反復した文字列を表す。

解説

文脈自由言語の反復補題(以下、単に反復補題と略記)は、全ての文脈自由言語が持つと保証されている属性を表している。その属性は、当該言語に含まれる長さ p 以上の全ての文字列について成り立つ。ここで、p は定数であり、反復長と呼ばれ、個々の文脈自由言語によって異なる。s が長さ p 以上の文字列とする。反復補題によれば、s は5つの部分文字列




英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「文脈自由言語の反復補題」の関連用語

文脈自由言語の反復補題のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



文脈自由言語の反復補題のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの文脈自由言語の反復補題 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2025 GRAS Group, Inc.RSS