• ベストアンサー
  • 困ってます

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

「オートマトン 言語理論 計算論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
  • 閲覧数740
  • ありがとう数1

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

  • ベストアンサー
  • 回答No.1
  • takebe
  • ベストアンサー率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に属さなくなりますので.

共感・感謝の気持ちを伝えよう!

質問者からのお礼

ありがとうございました。 そのとおりでした。 あとで気づいたのですが、自己レスつけれないので困ってたんです。 また何かありましたらよろしくお願いします。 (質問した段階ではパンピングレンマによる証明方法を勘違いしてました。)

関連するQ&A

  • 対偶による証明法と背理法による証明について

    数学Iの内容なのですが自分の使っている参考書に 対偶による証明法も一種の背理法と考えることが出来る。 命題p⇒qが真であることをいうために¬qと仮定して¬pが導かれたとする。 pではないからこれは矛盾で背理法が成立したことになる。 でも¬q⇒¬pとは文字通りこれは対偶のことで、これが真と言えたから 自動的に元の命題が真といってもいい と書いてあるのですが、色々な所で質問してみたのですが どうしてもあまり理解ができません。 (1)命題p⇒qが真であることをいうために¬qと仮定して¬pが導かれたとする 導かれた形は¬q⇒¬p 背理法の仮定の形では¬q⇒p (2)pではないからこれは矛盾で背理法が成立したことになる この導かれた形が¬q⇒¬pで命題の対偶の形をしていて それによっても命題が真であることが示されているから 対偶による証明法も一種の背理法と考えることが出来る、と書かれているのでしょうか?

  • 背理法について

    「a^2+b^2=c^3ならば、a、b、cのうち少なくとも1つは偶数である」 (pならばq) という命題を証明するために背理法を使います。 すると 「a^2+b^2=c^3という条件のもとで a、b、cはすべて奇数である」(pかつ¬q)と仮定することになると思います。 この仮定に矛盾が生じれば背理法が成立しますが この仮定に矛盾が生じるのは 「a,b,cが全て奇数ならば a^2+b^2=c^3 ではない」 (¬qならば¬p)が証明されたときだけなのでしょうか? まだ論理について勉強しはじめたばかりで記号があまり理解できないので 記号は使わずに説明していただけると助かります。

  • 背理法と対偶法について

    少し長くなるのですがお願いします。 私の使用している参考書に 「対偶による証明法も一種の背理法と考えることができる。 命題p→qが真であることをいうために¬q(qでない)と仮定して¬pが導かれたとする。 pではないからこれは矛盾で背理法が成立したことになる。 でも¬qならば¬pとは文字通り、これは対偶のことでこの対偶が真といえたから自動的に命題が真といってもいい」 と書かれていて この部分の意味がわからなかったので出版社に問い合わせました。 すると、このような回答を頂きました。 -------------------------------------------------------------------- 背理法は、 「pという前提条件下で、結論のqを否定して、¬qと仮定すると、矛盾が生じる。よって、p⇒q」とする論法ですね。対偶法において、この矛盾に相当するものが、 「¬pかつp」という矛盾です。なぜなら、¬q⇒¬pを示すのが対偶法だからです。 つまり、対偶:¬q⇒¬pが示されれば、この時点で「¬pかつp」という矛盾が生まれ、背理法が成立したことになります。 -------------------------------------------------------------------- 私は以前、この事に関する質問をここでして回答をいただいたのですが その時に頂いた回答をもとに考えたのがこの考え方です。 ---------------------------------------------------------------------- 「pならばq」を証明しようとしていて 「pならばq」に背理法を使って「pであって¬q」と仮定する。 その過程で「対偶 ¬qならば¬p」が証明できたとする。 「pであって¬q」と仮定しているのに対偶 ¬qならば¬p なので pではないため矛盾する。  よって「pならばq」は真である。 命題の対偶が証明された場合、普通は自動的に命題が真であると考えますが この説明文では 「命題の対偶が証明されたあと、背理法を使って命題が真であることを証明することになるので 対偶による証明法も一種の背理法と考えることが出来る」 ということが書かれている。 -------------------------------------------------------------------------- 出版社から頂いた回答と、この自分の考えが 合っているのか自信がもてません。 出版社にはこの事以外にも色々質問していて、何度もメールしづらいのでここで質問させてもらいました。 よろしくお願いします。 

  • 【数学I】不等式の証明問題

    家庭教師で高校1年の子の数学を教えているのですが、以下の問題でつまずいてしまいました。 0<a<1,0<b<1,0<c<1 ならば、 b(1-c)>1/4, c(1-a)>1/4, a(1-b)>1/4 は同時には成立しないことを示せ。 背理法で3式が同時に成立すると仮定して矛盾を導こうとしたもののうまく行きませんでした。 方針が間違っているでしょうか?木曜日に教えに行かなければならないので迅速な回答をしてくださった方にすぐに良回答をさしあげたいと思います。 どなたかよろしくお願いします。

  • 背理法による証明と対偶による証明法について

    自分の使っている参考書に 「対偶による証明法も一種の背理法と考えることができる。 命題p→qが真であることをいうために ̄q(qでない)と仮定して ̄pが導かれたとする。 pではないからこれは矛盾で背理法が成立したことになる。 でも ̄qならば ̄pとは文字通り、これは対偶のことでこの対偶が真といえたから自動的に命題が真といってもいい」 と書かれているのですがいまいち意味がわかりません。 どういうことなのでしょうか? 数1の内容なのですがあまり数学が得意ではないので簡単に教えていただけると助かります よろしくお願いします。

  • 背理法について

    今、学校の数学で背理法というのをやっているのですが、はっきり言って高校でやったきた問題の中で一番難しいというほど困っています。一応説明では「その命題が成り立たないと仮定すると矛盾が生じる。したがって、その命題が成り立たなければならない」という説明なのですがだいたい言っている意味はわかります。でも、実際に使って問題を解いてみると全くと言っていいほどできません(汗 仮定したあとに文字が出てきてそれを2乗したりなどなど… 背理法というものはだいたいわかったつもりだったのですが実際に使ってみると全然できなくて…途中の文字を用いて証明するところなど「どうしてこうなるの?」みたいなところばかりで全然前に進みません。 例えば、「自然数a,b,cがa^2+b^2=c^2を満たすならばa,b,cのなかに必ず偶数があることを背理法を用いて説明せよ」とい問題なのですが、解答を見ると、a^2+b^2=c^2を満たす自然数a,b,cがすべて奇数であると仮定すると、とあります。 どうもこのあたりの否定の置き方というのがよくわからないのです。必ず偶数がある、というのがすべて奇数であるになるのがさっぱりです。この辺りは国語的なものかもしれないのですが、このあたりでかなり苦戦しています。どなたか背理法を説明していただける方などおられましたらご回答お願いできないでしょうか?よろしくお願い致します。

  • 背理法

    問題 背理法を用いて、次の命題が真であることを示す。 命題:”√3は無理数である” ここで、背理法による証明はP→q や qであるが真であることをいうためにはまず ̄q(qではない)と仮定して矛盾を示すのでこの問題では、 √3は有理数であることを仮定しますが、 ここで有理数ということなので、整数、分数と改定しますが、なぜ既約分数で表すのでしょうか? 有理数は整数でもよいので 例えば、3やー4でもよいのでは? そこのところを教えてください。 疑問です。

  • PQ=Oについての証明

    背理法について(難) 2次正方行列P、Qについて、次のことを証明せよ。 PQ=O→P=OまたはQ=OまたはΔ(P)=Δ(Q)=0 指針 P284でも学んだように、行列においてはPQ=OであってもPnot=OであってもPnot=OかつQnot=Oとなることもある。 よって、この「Pnot=OかつQnot=O」の場合に,Δ(P)=Δ(Q)=0となることを示す。 直接は証明しにくいので背理法を利用する。 PQ=Oならば,P,Qについて,次の3つの場合がある。 [1]P=O [2]Q=O [3]Pnot=OかつQnot=O よって,[3]のとき⊿(P)=⊿(Q)=0となることを示す。 PQ=Oで[3]の場合,⊿(P)not=0と仮定すると,Pは逆行列を持つから,PQ=OからP^-1を掛けて P^-1PQ=P^-1O よってQ=O これはQnot=Oに矛盾するから⊿(P)=0 同様に,⊿(Q)not=0と仮定してもP=Oとなり,矛盾が生じる。 よって,PQ=O⇒P=OまたはQ=Oまたは⊿(P)=⊿(Q)=0 教えてほしいところ 要するに、Pnot=OかつQnot=O⇒⊿(P)=⊿(Q)=0を示す。 そのために⊿(P)not=0または⊿(Q)not=0が成り立たないことを示すということですよね。 何故、⊿(P)not=0を仮定して矛盾を導き、さらに,⊿(Q)not=0と仮定して矛盾を導くと⊿(P)not=0または⊿(Q)not=0が成り立たないと言えるんですか??? 誰か教えて下さい

  • √2が無理数であることの証明について

    √2が無理数であることの証明について 一つ疑問が生じまじた。 背理法を用いて、√2が有理数であると仮定すると、 √2=q/p (p,qは自然数)とおけるから 両辺二乗して 2=q^2/p^2 ⇒2*p^2=q^2 ・・・A ここから無限降下法を用いて矛盾を導くのが一般的な解法であると思うのですが、 Aの段階で明らかに(明らかでなくとも、証明すれば)右辺は平方数で左辺は平方数ではありません。 これは矛盾ではないのでしょうか? 例えば、平方数の約数の個数は奇数、非平方数の約数の個数は偶数ということをまず示せば、素因数分解の一意性に矛盾することは言えますが、そのような補題なしに「非平方数=平方数」は矛盾と考えてはいけないのでしょうか? 矛盾と考えていいのであれば一般の非平方数nに対して√nが無理数であることの証明がすごく簡単になるのですが・・・ 解説お願いします。

  • 言語の入門用例題を教えて下さい

    あなたの持っている言語の本に書いてある入門用プログラムの例題を教えて下さい。 例えば、K&Rの第1章に載っている入門用プログラムは以下の8つである。 1.hellow world 2.摂氏と華氏の変換 3.ファイルの複写 4.文字のカウント 5.単語のカウント 6.数字と空白文字とその他の文字の出現回数のカウント 7.ベキ乗の計算 8.1番長い行をプリントする 浦昭二編の「Fortran77入門」には以下の入門用の4つの例題プログラムが載っている。 1.電気料金の計算 2.整数の加減乗除 3.台形の面積 4.複利計算 このように、C言語以外の言語でもOKですが、あなたの持っている言語の入門用の本に書いてある入門用プログラムの例題と演習問題を教えて下さい。 よろしくお願いします。