言語理論の文脈自由言語について

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

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

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

ａ）｛ａ＾ｉ　ｂ＾ｊ　ｃ＾ｋ　｜　ｉ＜ｊ＜ｋ｝
　　「ｚ＝ａ＾ｎ　ｂ＾（ｎ＋ｌ）　ｃ＾（ｎ＋ｍ）　（但し、ｍ＞ｌ＞０）」

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

よろしくお願いします。

「言語を文脈自由言語と仮定する。
ｎをパンピングレンマの性質を持つ整数とし、
ｚ＝ａ＾ｎ　ｂ＾（ｎ＋ｌ）　ｃ＾（ｎ＋ｍ）　（但し、ｍ＞ｌ＞０）とすると、
ｚ∈Ｌ　かつ　｜ｚ｜≧ｎ　が成立する。
したがって、パンピングレンマから
ｚ＝ｕ　ｖ　ｗ　ｘ　ｙ　（ｕｘ≠ε、｜ｖｗｘ｜≦ｎ）
と表され、かつ
ｕ　ｖ＾ｉ　ｗ　ｘ＾ｉ　ｙ　∈　Ｌ
が成立する。
｜ｖｗｙ｜≦ｎ　なので、ｖｘがａとｃの両方を含むことはない。
ｖｘのパターンにより次の２つの場合を考える
（ｉ）ｖｘが一種類の文字だけからなる場合
…
（ｉｉ）ｖｘが２種類の文字からなる場合」

ここまで書いたところで、
ｖ＝ｂ、ｘ＝ｃ
とすると、例えば、
ｕ＝ａ、ｗ＝ｂｂ、ｙ＝ｃｃｃ
の場合を考えると、矛盾が導けないことに気付きました。

No.1 ベストアンサー 回答者： takebe 回答日時： 2001/05/11 18:00

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

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

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に属さなくなりますので．

この回答へのお礼

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

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

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