• 締切済み

文脈自由言語

１）文脈自由言語同士の和集合は文脈自由言語である。 ２）文脈自由言語に属す記号列の順序を反転させた記号列からなる言語は文脈自由言語である。 この２つのことを知識としては知っていたのですが、ただ漠然とそうなりそうだな、と思っていました。 しかし、どうしたら証明できるのでしょうか？証明の仕方など知ってる方がおられましたらご教授くださいませ。

みんなの回答

  • rinkun
  • ベストアンサー率44% (706/1571)
回答No.1

文脈自由言語(文脈自由文法)の定義を考えるとほとんど自明な気がしますが、いかが? 証明は構成したものが文脈自由文法の条件を満たすことを確認して記述するだけのように思います。

  1. カテゴリ
  2. 学問・教育
  3. 数学・算数

関連するQ&A

  • ある言語クラス判定問題(正規言語?文脈自由言語?)

    形式言語に関する以下の問題に悩んでおります。 問題: Lを正規言語とするとき、以下の言語L1, L2はそれぞれ(1)-(5)のどれに該当するか? L1={xy | xとyは共にLの元で、長さが同じ(|x|=|y|, x in L, y in L)} L2={xy | xとyは共にLの元で、xの長さはyの長さの2倍(|x|=2|y|, x in L, y in L)} (1)正規言語である (2)正規言語ではないが、文脈自由言語である (3)文脈自由言語ではないが、文脈依存言語である (4)文脈依存言語ではないが、帰納的可算言語である (5)帰納的可算言語ではない 直観的には(有限オートマトンは数を数えられないので)L1もL2も正規言語ではないと思うのですが、私の力では証明することが出来ないでおります。 ヒントや部分的回答(e.g. ひとまず(1)ではない。理由はかくかくしかじか)でもありがたいですので、どうぞよろしくお願いいたします。

  • 文脈自由文法についての質問です

    文脈自由文法についての質問です 最近、文脈自由文法について勉強しているんですがテキストの問題の中に 解き方がわからない問題があるので困ってます。 その問題が下に示してあるものです。 Q.次の文脈自由文法G=(V,T,S,P)は、本来は10進数の数値を受容する目的で作られたものであるが、 　この文脈自由文法には欠陥があり、10進数として読めるもの以外も受容してしまう。 　<S>を開始記号、<N>、<M>を非終端記号とする。 　 　規則P: 　<s> → <N> 　<N> → <M><N> | <M> | <N>.<N> 　<M> → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 　1.10進数以外の数値でも受容してしまう例を1つ示せ。 　2.1で示した例のように、10進の数値以外を受容してしまうような欠陥をなくすためには、 　　どのように文脈自由文法をの規則を変更すればよいか、変更後の規則をすべて示せ。 　 なお、非終端記号や終端記号は必要に応じて追加して良い。 　3.2で変更した文脈自由文法に対し、8進数を受容するにはどのように文脈自由文法の規則を 　　変更すればよいかを示せ この問題を解ける方がいましたら教えて頂きたいのでよろしくお願いします。 長文失礼しました。

  • 文脈自由文法についての質問です

    文脈自由文法についての質問です 最近、文脈自由文法について勉強しているんですがテキストの問題の中に 答えがわからない問題があるので困ってます。 その問題が下に示してあるものです。 Q.次の文脈自由文法G=(V,T,S,P)は、本来は10進数の数値を受容する目的で作られたものであるが、 　この文脈自由文法には欠陥があり、10進数として読めるもの以外も受容してしまう。 　<S>を開始記号、<N>、<M>を非終端記号とする。 　 　規則P: 　<s> → <N> 　<N> → <M><N> | <M> | <N>.<N> 　<M> → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 　1.10進数以外の数値でも受容してしまう例を1つ示せ。 　2.1で示した例のように、10進の数値以外を受容してしまうような欠陥をなくすためには、 　　どのように文脈自由文法をの規則を変更すればよいか、変更後の規則をすべて示せ。 　 なお、非終端記号や終端記号は必要に応じて追加して良い。 　3.2で変更した文脈自由文法に対し、8進数を受容するにはどのように文脈自由文法の規則を 　　変更すればよいかを示せ この問題を解ける方がいましたら教えて頂きたいのでよろしくお願いします。 長文失礼しました。

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

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

  • 文脈自由文法

    ・　<assugn>::=<id>=<expr> ・ <id>::=A|B|C ・　<expr>::=<expr>+<expr>|<expr>*<expr>|(<expr>)|<id> 問題 Ａ＝Ｂ＋Ｃ＊Ａの式を使って、上記文脈自由文法が「曖昧」であることを証明しなさい。 この問題を解答できる方がいましたら宜しくお願いします。 また合わせて解説していただけると大変助かります。 Ａ，Ｂ，Ｃの式というのが何を指しているのかも分からない状態です。 すみません、宜しくお願いします。

  • ジョルダン＝ヘルダーの定理について

    代数学のジョルダン＝ヘルダーの定理 『群Gが組成列をもつとき、その長さは一定であり、組成因子の集合｛Hi-1/Hi｝も同型と順序を除いて一意に定まる。』 の証明方法がわかりません、、、。 群Gが２つの組成列をもつとして、それらの長さが違うとして、、、と背理法で証明しようと思いましたが、どう結論に結び付けるのかわかりません。 証明の仕方をご教授お願いします。

  • 長文、有限のものの表現の仕方、集合・多重集合・文字列（順序対）

    有限のものがあったとします。 ・重複を許さない、順序を考えない、とします。 たとえば、aとbとcというものがあったとします。 これを表すのには、集合の記号を用いて、 {a,b,c} と表します。 ・重複を許す、順序を考える、とします。 たとえば、a,b,b,aという順にものがあったとします。 これは順序対の記号を用いて、 (a,b,b,a) と表すと思います。 また、文字列とみなして、 abba と表すこともあると思います。0から9の数字と+-記号を用いて、整数を表すのもこれに相当するとおもいます。 順序対の記号は、たとえば http://oshiete1.goo.ne.jp/qa2861763.html にあるように、集合の記号によって定義することもできます。 質問１．では逆に、集合の記号を、順序対の記号によって定義することはできるのでしょうか？ ・重複を許す、順序を考えない、とします。 たとえば、aが2個、bが3個、cが1個というものがあったとします。 これは多重集合の考え方ですが、 {|aa,bbb,c|} と表したりするようです。 質問２．多重集合を、集合の記号や順序対の記号を用いて、うまく表すことはできないものでしょうか? ・重複を許さない、順序を考える、とします。 たとえば、a,c,b,d,eという順にものがあったとします。 質問３．しかし、この考え方の具体的な名前、応用例、表し方を知らないので、教えていただきたいのです。 それは順序対の記号を用いて、 (a,c,b,d,e) と表せばいいという方がいるかもしれませんが、その記号だと、重複を許さないという考えを伝えることができないので、よくはないと思うのです。

  • 本物の要素関係∈と言語としてのεの関係

    再質問になります、御容赦ください。 「数とは何かそして何であるべきか」や「ゲーデルと２０世紀の論理学　４」などにおいて 集合論の言語として｛ε｝を用いる、ただしεは２変数関係記号である。体系の外で考えているとき、あるいは集合論のモデルで考えているときの、「本当の」要素関係∈と区別するためこの記号を使用する とあり、言語記号としてのεと実際の要素関係を表す∈を区別しています、しかしこの区別はどういう意味があるのでしょうか。 記号そのものと、それが表現するものの違いだ、と一旦は分かった気になるのですが、さらに考えてみると本物の要素関係∈なるものも何らかの公理と推論規則、つまり形式体系で書かれるしかないのではないか？ならばそれも言語記号と違わないのでは？と堂々巡りになっていますのです。（この二つの記号はいつも同じ内容を表すとは限らないために区別しているのだ、と考えても両者とも結局包含関係を表す訳で・・・、二者の間に意味の違いがあるという状況を想像出来ないのです。） また、 「体系の言語で記述される（内的な）無限降下列 とモデルでの無限降下列の区別」と http://kurt.scitec.kobe-u.ac.jp/~fuchino/foundation.html　（渕野 昌先生） にある文章においても（同じことだと思うのですが、）悩んでおり、その区別がいかなるものか分かっていません。 「本物の」要素関係なるものが記述はされないが存在する　などと言うことではないと感じるのですが・・・。 おそらくはじめの部分で勘違いをしていると思います、しかし、それがどういうものなのかはっきりしておらず苦しんでおります、この方面に明るい方助けていただければ幸いです。

  • 言語としてのεと本物の包含関係∈の違いについて

    「数とは何かそして何であるべきか」や「ゲーデルと２０世紀の論理学　４」などにおいて 集合論の言語として｛ε｝を用いる、ただしεは２変数関係記号である。体系の外で考えているとき、あるいは集合論のモデルで考えているときの、「本当の」要素関係∈と区別するためこの記号を使用する とあり、言語記号としてのεと実際の要素関係を表す∈を区別しています、しかしこの区別はどういう意味があるのでしょうか。 記号そのものと、それが表現するものの違いだ、と一旦は分かった気になるのですが、さらに考えてみると本物の要素関係∈なるものも何らかの公理と推論規則、つまり形式体系で書かれるしかないのではないか？ならばそれも言語記号と違わないのでは？と堂々巡りになっていますのです。（この二つの記号はいつも同じ内容を表すとは限らないために区別しているのだ、と考えても両者とも結局包含関係を表す訳で・・・、二者の間に意味の違いがあるという状況を想像出来ないのです。） また、 「体系の言語で記述される（内的な）無限降下列 とモデルでの無限降下列の区別」と http://kurt.scitec.kobe-u.ac.jp/~fuchino/foundation.html　（渕野 昌先生） にある文章においても（同じことだと思うのですが、）悩んでおり、その区別がいかなるものか分かっていません。 「本物の」要素関係なるものが記述はされないが存在する　などと言うことではないと感じるのですが・・・。 おそらくはじめの部分で勘違いをしていると思います、しかし、それがどういうものなのかはっきりしておらず苦しんでおります、この方面に明るい方助けていただければ幸いです。

  • word２００７に自由に回転が無くて困ってます

    word２００７を使ってます。 word２００３にある、図形の調整→回転/反転→自由に回転を重宝してましたが,woord２００７には同じ様な機能は無いのでしょうか？ どなたかご存知の方、ご教授お願いします。

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

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

質問する