「オートマトン 言語理論 計算論I」という本(教科書)を読んでいます。
この本には演習問題がついているのですが、本を読んだだけでは解法が分らない上、
答えがついてないため、解けない問題が多く困っています。
(連休明けに試験があり、その範囲なんです。)

ある言語が文脈自由型ででないことを証明したいのですが、
反復補題(パンピングレンマ)を用いて背理法によるのだろうと思うのですが、
どのように仮定するかの方針が立たないのです。

具体的には次のような問題に対し、「…」のような仮定をしてみました。

a){a^i b^j c^k | i<j<k}
  「z=a^n b^(n+l) c^(n+m) (但し、m>l>0)」

しかし、下記のように背理法による矛盾が示せなかったのです。
どこで間違ったのかは分らないので、間違った個所を指摘していただきたいのです。

よろしくお願いします。

「言語を文脈自由言語と仮定する。
nをパンピングレンマの性質を持つ整数とし、
z=a^n b^(n+l) c^(n+m) (但し、m>l>0)とすると、
z∈L かつ |z|≧n が成立する。
したがって、パンピングレンマから
z=u v w x y (ux≠ε、|vwx|≦n)
と表され、かつ
u v^i w x^i y ∈ L
が成立する。
|vwy|≦n なので、vxがaとcの両方を含むことはない。
vxのパターンにより次の2つの場合を考える
(i)vxが一種類の文字だけからなる場合

(ii)vxが2種類の文字からなる場合」

ここまで書いたところで、
v=b、x=c
とすると、例えば、
u=a、w=bb、y=ccc
の場合を考えると、矛盾が導けないことに気付きました。

A 回答 (1件)

連休明けに試験があるとのことで,もう手遅れかもしれませんが...



パンピングレンマですが,

z = uvwxy

となるu,v,w,x,yが1つは存在する,というものと思われます(あまり詳しくないです).

unicorn01さんが仮定したz=a^n b^(n+l) c^(n+m)に対して,v=bとなるものが存在するかというと,必ずしもそうではないのではないでしょうか.

実際,z=a^n b^(n+1) c^(n+2)に対して,v=bというものは存在しないですね.iが0の時にLに属さなくなりますので.
    • good
    • 0
この回答へのお礼

ありがとうございました。 そのとおりでした。
あとで気づいたのですが、自己レスつけれないので困ってたんです。
また何かありましたらよろしくお願いします。

(質問した段階ではパンピングレンマによる証明方法を勘違いしてました。)

お礼日時:2001/05/11 19:30

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード


このカテゴリの人気Q&Aランキング

おすすめ情報

カテゴリ