オグデンの補題

ウィキペディア

オグデンの補題

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2014/10/11 21:26 UTC 版)

オグデンの補題（英: 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 について uvⁱxyⁱz は L に含まれる。

オグデンの補題は、文脈自由言語の反復補題では示せない場合でも、特定の言語が文脈自由でないことを示すことができる。例えば、言語 {aⁱb^jc^kd^l : i = 0 or j = k = l} がそのような言語である。

全位置（文字）がマークされるとき、この補題は文脈自由言語の反復補題と等価になる。

関連項目

• 反復補題
• 文脈自由言語の反復補題
• 正規言語の反復補題

参考文献

• Ogden, W. (1968年). “A helpful result for proving inherent ambiguity”. Mathematical Systems Theory 2: 191–194. . 
• Hopcroft, Motwani and Ullman (1979年). Automata Theory, Languages, and Computation. Adison Wesley.