言語理論の文脈自由言語とは？　背理法を用いた証明の方法とは？

前へ 次へ
このQ&Aのポイント
  • 言語理論の文脈自由言語について説明します。また、背理法を用いて文脈自由言語でないことを証明する方法についても解説します。
  • 演習問題に取り組む際、解法が分からず困っています。具体的には文脈自由言語でないことを証明する問題に取り組んでいますが、仮定の立て方が分からず解けません。
  • 仮定を立てて証明を進めた結果、矛盾が導けないことに気付きました。どこで間違えたか分からないので、間違いを指摘していただきたいです。
回答を見る
  • ベストアンサー

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

「オートマトン　言語理論　計算論Ｉ」という本（教科書）を読んでいます。 この本には演習問題がついているのですが、本を読んだだけでは解法が分らない上、 答えがついてないため、解けない問題が多く困っています。 （連休明けに試験があり、その範囲なんです。） ある言語が文脈自由型ででないことを証明したいのですが、 反復補題（パンピングレンマ）を用いて背理法によるのだろうと思うのですが、 どのように仮定するかの方針が立たないのです。 具体的には次のような問題に対し、「…」のような仮定をしてみました。 ａ）｛ａ＾ｉ　ｂ＾ｊ　ｃ＾ｋ　｜　ｉ＜ｊ＜ｋ｝ 　　「ｚ＝ａ＾ｎ　ｂ＾（ｎ＋ｌ）　ｃ＾（ｎ＋ｍ）　（但し、ｍ＞ｌ＞０）」 しかし、下記のように背理法による矛盾が示せなかったのです。 どこで間違ったのかは分らないので、間違った個所を指摘していただきたいのです。 よろしくお願いします。 「言語を文脈自由言語と仮定する。 ｎをパンピングレンマの性質を持つ整数とし、 ｚ＝ａ＾ｎ　ｂ＾（ｎ＋ｌ）　ｃ＾（ｎ＋ｍ）　（但し、ｍ＞ｌ＞０）とすると、 ｚ∈Ｌ　かつ　｜ｚ｜≧ｎ　が成立する。 したがって、パンピングレンマから ｚ＝ｕ　ｖ　ｗ　ｘ　ｙ　（ｕｘ≠ε、｜ｖｗｘ｜≦ｎ） と表され、かつ ｕ　ｖ＾ｉ　ｗ　ｘ＾ｉ　ｙ　∈　Ｌ が成立する。 ｜ｖｗｙ｜≦ｎ　なので、ｖｘがａとｃの両方を含むことはない。 ｖｘのパターンにより次の２つの場合を考える （ｉ）ｖｘが一種類の文字だけからなる場合 … （ｉｉ）ｖｘが２種類の文字からなる場合」 ここまで書いたところで、 ｖ＝ｂ、ｘ＝ｃ とすると、例えば、 ｕ＝ａ、ｗ＝ｂｂ、ｙ＝ｃｃｃ の場合を考えると、矛盾が導けないことに気付きました。

  • 科学
  • 回答数1
  • ありがとう数1

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

  • ベストアンサー
  • takebe
  • ベストアンサー率65% (17/26)
回答No.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に属さなくなりますので．

unicorn01
質問者

お礼

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

  1. カテゴリ
  2. 学問・教育
  3. 自然科学
  4. 科学

関連するQ&A

  • ポインタを使ったＣ言語

    (1)、(2)、(3)に何が入るか教えてください。 void main() { char *pt[(1)]: char member[][(2)]={ {'C','a','u','d','y','\0',}, {'N','a','n','c','y','\0',}, {'E','l','u','z','a','\0',}, }; (3) } 実行結果 [C N E] [a a l] [u n u] [d c z] [y y a]

  • Ｃ言語を使ったプログラム作成

    ご教授お願い致します。 void main() { char *pt[3]; char member[][6]={{'C','a','n','d','y','\0'}, {'N','a','n','c','y','\0'}, {'E','l','u','z','a','\0'}, }; pt[0]=member[0]; pt[1]=member[1]; pt[2]=member[2]; printf("[%c %c %c]\n",(*pt[0]++),*(pt[1]++),*(pt[2]++)); } 実行結果 [C N E] [a a l] [n n u] [d c z] [y y a] となるのですが以降文字がないところはスペースにするにはどうすればいいでしょうか。 例　実行結果　※△＝スペース [C△N△ E] [a△a△l] [n△n△u] [d△c△z] [y△y△a] [1△1△1] [2△2△△] [3△△△△] [△△△△△] [△△△△△]

  • C言語の配列の使い方について質問です。

    以下のプログラムを配列を使って見やすくしたいのですが、どのように作ったら良いでしょうか？ 宜しくお願いします。 #include<stdio.h> int main(void) { int a, b, c, d, e, f, g, h, i, j, k, l, m ,n, o; /*5段目の処理*/ for(a = 1; a <= 15; a++) { for(b = 1; b <= 15; b++) { if(a == b) continue; for(c = 1; c <= 15; c++) { if(a == c || b == c) continue; for(d = 1; d <= 15; d++) { if(a == d || b == d || c == d) continue; for(e = 1; e <= 15; e++) { if(a == e || b == e || c == e || d == e) continue; // printf("%d %d %d %d %d\n", a, b, c, d, e); ////4段目//// if(a>b){ f=a-b; } else if(a<b){ f=b-a; } if(b>c){ g=b-c; } else if(b<c){ g=c-b; } if(c>d){ h=c-d; } else if(c<d){ h=d-c; } if(d>e){ i=d-e; } else if(e<d){ i=e-d; } // printf(" %d %d %d %d \n", f, g, h, i); /////3段目//// if(f>g){ j=f-g; } else if(f<g){ j=g-f; } if(g>h){ k=g-h; } else if(g<h){ k=h-g; } if(h>i){ l=h-i; } else if(h<i){ l=i-h; } // printf(" %d %d %d \n", j, k, l); /////2段目//// if(j>k){ m=j-k; } else if(j<k){ m=k-j; } if(k>l){ n=k-l; } else if(k<l){ n=l-k; } // printf(" %d %d \n", m, n); /////三段目///// if(m>n){ o=m-n; } else if(m<n){ o=n-m; } // printf(" %d \n", o); if(a != b != c != d != e != f != g != h != i != j != k != l != m != n != o){ printf("%d %d %d %d %d\n", a, b, c, d, e); printf(" %d %d %d %d \n", f, g, h, i); printf(" %d %d %d \n", j, k, l); printf(" %d %d \n", m, n); printf(" %d \n", o); } } } } } } }

  • 数A　集合

    【問題】 A=｛１２ｍ＋８ｎ｜ｍ∈Z、ｎ∈Z｝、B=｛４ｌ｜ｌ∈Z｝とする。 A=Bであることを示せ。 ただし、Z=｛整数全体｝ 私は A＝｛１２ｍ＋８ｎ｜ｍ∈Z、ｎ∈Z｝ 　＝｛４（３ｍ＋２ｎ）｜ｍ∈Z、ｎ∈Z｝ ここで、３ｍ＋２ｎ＝ｌとおくと、A＝｛４ｌ｜ｌ∈Z｝＝B よって、A=Bが成り立つ としたのですが、解答では *－*－*－*－* ｘ∈Aならば、ある整数ｍ、ｎについて、 　ｘ＝１２ｍ＋８ｎ＝４（３ｍ＋２ｎ）とあらわせる。 ここで、３ｍ＋２ｎが整数より、ｘ∈Bが成り立つ。 したがって、A⊂B・・・(1) また、ｘ∈Bならば、ある整数ｌについて、 　ｘ＝４ｌ＝４（３－２）ｌ 　　　　 ＝１２ｌ＋８・（－ｌ）と表せる。 ここで、ｍ＝ｌ、ｎ＝－ｌとおくと、ｍ、ｎは整数で、ｘ＝１２ｍ＋８ｎと表せるから、ｘ∈A したがって、B⊂A・・・(2) (1)、(2)より、A=B *－*－*－*－* となっていました。 やはり、ｘ∈A⇒ｘ∈Bとｘ∈B⇒ｘ∈Aを示し、必要十分性を確かめる解答にしなくてはいけないのでしょうか？ やはり私の解答では証明したことにはならないのでしょうか？

  • オートマトンの反復補題。

    {xx^r | x∈Ｔ^*} (x^rはxと文字列が逆さま。つまりxx^rは回文) が正規言語でないことを証明せよという問題で、他の問題を参考にして自分ではこう考えました。 Lが正規言語と仮定し、状態数nについて、 z = a^nb^nb^na^n を考える。 |z|>n であり、 z = uvw ,|uv|≦n ,|v|≧1　となるu,v,wが存在して 任意のiについて、 uv^iw ∈ L 今i=0とおく。v=a^k　(k≧1)であるから、 uw中のaの数は n + n-k uw中のbの数は n + n よってa^nb^nb^na^nはaとbの数が等しくないといけないから uw ∈　Ｌ　に矛盾。 よってＬは正規言語ではない。 これはあってますか？回答がないため、確認する手段がなく困っています。 もし違っていればその箇所をご指摘ください。

  • DirichletのL関数がs=1で正則となるのは

    s∈C,χはχ(Z_m^×)≠{1}なるDirichlet指標とする時, DirichletのL関数 L(s,χ)=Σ_{a=1}^{m-1}χ(a)/(m^s lim_{n→∞}n^s n!/Π_{k=0}^n(s+k))[Σ_{n=0}^∞(-1)^n B_n(a/m)/(n!(s+n-1))+∫_1^∞exp(-au/m)u^{s-1}/(1-exp(-u)) du] (但し,B_n(a/m)はn次のBernoulli多項式) がs=1で正則となる事の証明で質問です。 s=0,-1,-2,…の時はn^s n!/Π_{k=0}^n(s+k))の零点とΣ_{n=0}^∞(-1)^n B_n(a/m)/(n!(s+n-1))の極が打ち消しあって, 正則になる事は分かるのですがs=1の時は打ち消しあえないのでχ(Z_m^×)≠{1}という条件を使うのだと思います。 どのようにχ(Z_m^×)≠{1}を利用すればいいのでしょうか?

  • 線形代数　＊大至急お願いします

    次の連立方程式を解け（行列で） 2y＋4z＋2u=2 -x＋y＋3z＋2u=2 x＋2y＋3z＋u=a（aはパラメーター） -2x-y＋u=1 これをやるとどうしても同じ数字の並びが出てきてしまいます。 行列式の因数分解 a b c d b a d c c d a b d c b a これを Ａ＝a b b a Ｂ＝c d d c とおいて解いて見たのですが答えになりません。 m ΣaIx^i （i=0） と ｎ ΣbIx^j j=0 IとＪは添え字です。 これら２つ積のx^kの係数は？？ 次の不等式を示せ rank(A)＋rank(B)<=rank(AB)＋ｍ Ａ（l,m）型行列、Ｂ(m,n)型行列 途中式をわかりやすくお願いします。

  • C言語でのFFTについて

    http://tsuyu.cocolog-nifty.com/blog/2007/03/publi.html に掲載されているVBAのFFTプログラムをC言語に書き換えて 実行しているのですがうまくいきません。 どこが、間違っているか教えてください。 ＝＝＝＝＝＝以下FFTのサブルーチンソースコード＝＝＝＝＝ void FFT(float Xr[], float Xi[]) { i=0,j=0,k=0,l=0,m=0,n=0,p=0,q=0; n=DN; m = log10(n)/log10(2); Table(c,s); l=n,h=1; for(g=1;g<=m;g++){ l/=2,k=0; for(q=1;q<=h;q++){ p=0; for(i=k;i<=l+k-1;i++){ j=i+l; a=Xr[i]-Xr[j], b=Xi[i]-Xi[j]; Xr[i] = Xr[i] + Xr[j], Xi[i] = Xi[i] + Xi[j]; if(p==0){ Xr[j]=a,Xi[j]=b; }else{ Xr[j] = a * c[p] + b * s[p], Xi[j] = b * c[p] - a * s[p]; } p+=h; } k+=l+l; } h+=h; } j=n/2; for(i=1;i<=n-1;i++){ k=n; if(j<i){ //ビットリバース swap(&Xr[i],&Xr[j]); swap(&Xi[i],&Xi[j]); } k=k/2; while(j>=k){ j=j-k; k /=2; } j = j + k; } }

  • ３次元の三角形平面の内挿

    空間に三角形があります。 座標(x1,y1,z1),(x2,y2,z2),(x3,y3,z3) 値は(u1,u2,u3) 三角形平面内の場所x,y,z（例えば重心）を入れたらその値uが求まるようにしたいです。 つまり u=N1 u1 + N2 u2 + N3 u3 となるときの N1=a1 x +b1 y + c1 z + d1 N2=a2 x +b2 y + c2 z + d2 N3=a3 x +b3 y + c3 z + d3 の a1,a2,a3,b1,b2,b3,c1,c2,c3,d1,d2,d3を求めたいです。 ２次元平面の三角形はよいのですが、３次元平面の三角形は分かりません。 よろしくお願いいたします。

  • 【C言語】入力された文字種別ごとにカウント

    以下のように実行したいのですが、 どのように組んだら良いのでしょうか？ 宜しくお願いします。 言語はC言語で、環境はVisual C++ 2010 Express Editionを使っています。 ちなみに最後の方に現在のコードがあります。 ///////////////////////////////////////////// 文字を入力しなさい（終了条件：Ctrl+Z） abcdef678ABCDEFopuKLH ghtJK+ghjBBBdgjk ^Z a : 1個入力 b : 1個入力 c : 1個入力 d : 2個入力 e : 1個入力 f : 1個入力 g : 3個入力 h : 2個入力 i : 0個入力 j : 2個入力 k : 1個入力 l : 0個入力 m : 0個入力 n : 0個入力 o : 1個入力 p : 1個入力 q : 0個入力 r : 0個入力 s : 0個入力 t : 1個入力 u : 1個入力 v : 0個入力 w : 0個入力 x : 0個入力 y : 0個入力 z : 0個入力 A : 1個入力 B : 4個入力 C : 1個入力 D : 1個入力 E : 1個入力 F : 1個入力 G : 0個入力 H : 1個入力 I : 0個入力 J : 1個入力 K : 2個入力 L : 1個入力 M : 0個入力 N : 0個入力 O : 0個入力 P : 0個入力 Q : 0個入力 R : 0個入力 S : 0個入力 T : 0個入力 U : 0個入力 V : 0個入力 W : 0個入力 X : 0個入力 Y : 0個入力 Z : 0個入力 /////////////////////////////////////// #include <stdio.h> #include <conio.h> #define ALPHABET_COUNT 52 int main(void) { // 入力アルファベットの個数を数えるカウンタは大きさ 52 の配列で用意。 int counter[ALPHABET_COUNT]; int c; int i; // 最初に、配列の 52個の要素すべてを0クリアする for(i=0;i<52;i++){ counter[i] = 0; } printf("文字を入力しなさい（終了条件：Ctrl+Z）\n"); while(1){ c = getchar(); if(c == EOF){ break; } if(c >= 'a' && c <= 'z'){ //65<90 counter[c-'a']++; } else if(c >= 'A' && c <= 'Z'){ //97<122 counter[c-'A']++; } } // 文字種別の個数表示する c = 'a'; for(i=0;i<ALPHABET_COUNT;i++){ if(i<26){ printf("\t%c : %3d個入力",c++,counter[i]); if(((i+1)%3) == 0){ printf("\n"); } } else{ if(i==26){ printf("\n"); c = 'A'; } printf("\t%c : %3d個入力",c++,counter[i]); if(((i+2)%3) == 0){ printf("\n"); } } } printf("\n"); /* c = 'a'; for(i=1;i<=26;i++){ printf("\t%c : %3d個入力",c++,counter[i-1]); if(i%3 == 0){ printf("\n"); } } printf("\n"); */ }

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する