-PR-
解決済み

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

  • 困ってます
  • 質問No.71578
  • 閲覧数638
  • ありがとう数1
  • 気になる数0
  • 回答数1
  • コメント数0

お礼率 68% (31/45)

「オートマトン 言語理論 計算論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
の場合を考えると、矛盾が導けないことに気付きました。
通報する
  • 回答数1
  • 気になる
    質問をブックマークします。
    マイページでまとめて確認できます。

質問者が選んだベストアンサー

  • 回答No.1
レベル8

ベストアンサー率 65% (17/26)

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

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

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に属さなくなりますので.
お礼コメント
unicorn01

お礼率 68% (31/45)

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

(質問した段階ではパンピングレンマによる証明方法を勘違いしてました。)
投稿日時 - 2001-05-11 19:30:58
-PR-
-PR-
このQ&Aのテーマ
このQ&Aで解決しましたか?
AIエージェント「あい」

こんにちは。AIエージェントの「あい」です。
あなたの悩みに、OKWAVE 3,500万件のQ&Aを分析して最適な回答をご提案します。

関連するQ&A
-PR-
-PR-
このQ&Aにこう思った!同じようなことあった!感想や体験を書こう
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。

その他の関連するQ&A、テーマをキーワードで探す

キーワードでQ&A、テーマを検索する
-PR-
-PR-
-PR-

特集


専門家があなたの悩みに回答!

-PR-

ピックアップ

-PR-
ページ先頭へ