|
文脈自由言語の反復補題（ぶんみゃくじゆうげんごのはんぷくほだい、）は、全ての文脈自由言語が持つ属性を与える反復補題である。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 」があります。 スポンサード リンク
|