Ogdenの補題

投稿日 2017-03-03 05:55 投稿者 test 数学

証明がわかりません、、、


1件の回答


具体的には次の通りである。言語 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 に含まれる。
オグデンの補題は、文脈自由言語の反復補題では示せない場合でも、特定の言語が文脈自由でないことを示すことができる。例えば、言語 {aibjckdl : i = 0 or j = k = l} がそのような言語である。
全位置(文字)がマークされるとき、この補題は文脈自由言語の反復補題と等価になる。

回答者 fuckyou 2017-03-04 00:23
回答するにはログインする必要があります。