締切済み

文脈自由言語についての質問です。よろしく　お願いします

2010/08/13 00:51

この投稿のマルチメディアは削除されているためご覧いただけません。

chujunshi
お礼率24% (9/37)

ハードウェア・サーバー
回答数1
ありがとう数1

みんなの回答 （1）
専門家の回答

みんなの回答

Tacosan
ベストアンサー率23% (3656/15482)

2010/08/14 01:08 回答No.1

ぶっちゃけどこが「ハードウェア (サーバ)」なのか皆目見当がつかないのだが, 例えば L = { w^R w | w ∈ { 0, 1 }^* } ならできるか?

質問者

お礼 2011/07/21 00:03

ありがとうございます

関連する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進数を受容するにはどのように文脈自由文法の規則を　　変更すればよいかを示せこの問題を解ける方がいましたら教えて頂きたいのでよろしくお願いします。長文失礼しました。
言語理論の文脈自由言語について

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

初めまして。最近、コンパイラの学習を始めた初心者です。よろしくお願いいたします。ある文献には、「BNF表記は文脈自由文法を表す」と書かれています。これは、BNF表記が表す文法と文脈自由文法が等価と文字通り理解していいものなのでしょうか？（つまり、BNF表記された文法は全て文脈自由文法で、文脈自由文法は全てBNF表記で表すことができる、ということなのかです。）また文脈“自由”文法があるのであれば、文脈“依存”文法というもの存在するのでしょうか？以上2点につきまして、ご回答よろしくお願いいたします。
文脈自由文法

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

みなさん、はじめまして＾＾ ”文脈’という単語は、辞書そう書いてありますが：ぶん-みゃく [0] 【文脈】（１）文における個々の語または個々の文の間の論理的な関係・続き具合。文の脈絡。コンテクスト。「前後の―から意味を判断する」（２）一般に，すじみち・脈絡。また，ある事柄の背景や周辺の状況。私はある友達と下記ような対話をしましたが。。。。友達：”うまい”の意味は何ですか？私：”delicious"です。友達：そうですか、でもそんな翻訳は私の場合にはふさわしくないと思いますが。私：文脈は？友達：”文脈”？どういう意味？。。。。。。。。。私は”文脈は”と言ったのは、つまり文脈を見てから、その場合にふさわしい翻訳をできるということですが、どうして友達はわからないですか。私はどこか間違えていたのか？教えてください、どうも＾＾
単語は文脈で覚えるべき？

単語は文脈で覚えるべき？こんにちは、このカテでもどうやったら英単語を効率よく覚えられるかという質問が出されます。そして、文脈で覚えたほうがいいという意見もよく聞きます。私は中学、高校と英単語は比較的すらすら覚えられましたので、単語で苦労した思い出はあまりないのですが、必ずしも単語は文脈で覚えるのが正しいのか疑問を感じるようになりました。というのは、私はスペイン語を勉強しているのですが、文脈に頼った覚え方だと出会ったことのある単語でも文脈が違ってくると度忘れしたように意味がピンと浮かんでこなかったり、特に作文なんかをする時に、単語があやふやだったりすることが往々にしてあります。そこで質問です。単語をおぼえるには、やはり単語だけを個別に一つずつ潰していくことも大事ではないでしょうか？
文脈

good nightが文脈によって have a good nightの意味になったりするのは分かるのですが England is mine and it owe me a living 「イングランドは僕のもの　その生死は僕にかかっている」「イングランドの未来は　僕のような若者にかかっているというが　実際は逆で僕がイギリスのお世話になっている」この二つの訳は　文脈によってはどちらも正しいのですか？あるいは　文脈と関係なくどちらも正しいですか？それともどちらかが間違いですか？
例文集からの質問です。（よって文脈とかはありません）

例文集からの質問です。（よって文脈とかはありません） Credit cards will have to do. （クレジットカードで大丈夫です。）慣用表現として丸暗記してもよかったのですが、この文のhave to がなぜ必要なのか、説明できる方がいらっしゃったらよろしくお願いします。
多重文脈性とは…？

「関与シールドとしてのケータイの利用が、多重文脈性をまとう」というのはどういう意味ですか？　多重文脈性の意味だけでもいいので教えてください。
英語ってどういう言語ですか？

こんな日本語があるとします。・いったよ。・みてもらったよ。・うえのほう？・あしたかな。・まぁ、そう。・ことしいやなよかんあたるきする　するする　いや～！適当に半端な日本語を書きましたが、全部意味が分かりますよね？一方、英語だと、何年も前から思ってたことですが、文脈が無いと意味が取れない、と言う事態に遭遇しますよね？してもらったのか、させたのか、も、ひょっとしたら分からないし、成功したのか、それを作ったのかも、分かりませんよね。英語って、文脈が無いとネイティブでも、何が言いたいか分からない言語なんですか？よくこんな言語で会話できるなぁと思うことがありました。母に宿題を手伝ってもらった、が、母に宿題を手伝わせた、とも取れるんですよね？英語って、そういう言語なんですか？それとも、ネイティブは、ちゃんと明確に区別できるのですか？前後がなくても。
非断定的文脈と断定的文脈の違い　英語

英語での非断定的文脈と断定的文脈の違いが理解できないです。例を交えて解説して下さると幸いです。お願いします。
文脈がわかりません

「行動心理学（行動主義心理学）とは、心理学のアプローチの1つです。全く合理的に見えない人間の行動の背景には環境や遺伝が隠れている、つまり「意志」は錯覚である、というのが行動心理学の主張の1つです。」という風な文を見かけたのですが、この文脈がいまいちわかりません。なぜ人間の行動の背景には環境や遺伝が隠れているということ＝意思の錯覚となるのでしょうか？
ｗｅｂを自由自在に操作しやすいプログラミング言語は

ｗｅｂを自由自在に操作しやすいプログラミング言語は？今はｖｂａでIEを立ち上げログインしたり、欲しいデータを取得したりしてるのですがＶＢＡよりも操作度が高くて、細かい事までできるプログラミング言語はありますか？
分数における「1」の意味は文脈によって変わる？

分数における「1」の意味は文脈によって変わる？たとえばケーキについて、文脈によって2個を１と捉えることもできるし、１０個を１と捉えることもできるのでしょうか？そうであるならば、その例を示していただけると幸いです。
文脈自由文法をチョムスキー標準形に変換

大学の数学で分からない問題があります。どなたか教えていただけないでしょうか？１．次の規則を持つ文脈自由文法をチョムスキー標準形に変換せよ。 (1) G=({S,A},{ab},P,S) P={S→Ab,A→aAb,A→ab} (2) G=({S,A,B},{ab},P,S) P={S→aB,S→bA,A→a,A→aS,A→bAA,B→b,B→bS,B→aBB} (3) G=({S},{a,b},P,S) P={S→aS,S→aSbS,S→ε} ２．次の書き換え規則で定義される文法が生成する言語を示せ。　　但し、「={S,A,B},Σ={0,1,2},開始記号はSとする。 (1) S→0AB,A→0AB|0B,B→1 (2) S→S0|AB,A→1A|1,B→2 (3) S→A,A→0A|0,B→B1|1 (4) S→AB.A→0A1|01,B→B2|2 問題は以上です。長くなってしまい申し訳ありません。また、学校で何やっていたんだとお怒りの方もいらっしゃるかと思いますが、何卒よろしくお願いします。
環境的文脈効果（匂い）の記憶実験に自由再生課題を用いるわけを教えてくだ

環境的文脈効果（匂い）の記憶実験に自由再生課題を用いるわけを教えてください。また、その時にどうして絵画、数字、外国語を使用せずに仮名や漢字を使うのはどうしてですか？また仮名と漢字、どちらがベストなのですか？
文脈がわかりません

本を読んでいたのですが、文脈がよくわかりませんでした。「ある村に、床屋さんが一人だけいた。その床屋さんは、自分自身のひげをそらない人全員のひげをそるとする。さてこの床屋さん自身のひげは誰がそる？　自分でひげをそるとしたら、この床屋さんは自分のひげをそらない人をそるはずだから矛盾してしまう。自分のひげをそらないとすると、この床屋さんは自分自身のひげをそらない人、全員のひげをそるわけだからこちらも矛盾する・・・。そう、解決できないジレンマに陥りますよね。」と書いていたんですが、ややこしくて何言ってるかよくわかりません。もうすこしわかりやすく解説していただけないでしょうか。お願いします。

文脈自由言語についての質問です。よろしく　お願いします

みんなの回答

お礼 2011/07/21 00:03

関連するQ&A

文脈自由言語

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

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

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

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

BNF表記と文脈自由文法の関係について

文脈自由文法

”文脈’の使い方に教えていただけませんか？

単語は文脈で覚えるべき？

文脈

例文集からの質問です。（よって文脈とかはありません）

多重文脈性とは…？

英語ってどういう言語ですか？

非断定的文脈と断定的文脈の違い　英語

文脈がわかりません

ｗｅｂを自由自在に操作しやすいプログラミング言語は

分数における「1」の意味は文脈によって変わる？

文脈自由文法をチョムスキー標準形に変換

環境的文脈効果（匂い）の記憶実験に自由再生課題を用いるわけを教えてくだ

文脈がわかりません

注目のQ&A

カテゴリ
一覧

専門家に質問してみよう
専門家登録

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

文脈自由言語についての質問です。よろしく お願いします

みんなの回答

お礼 2011/07/21 00:03

関連するQ&A

文脈自由言語

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

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

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

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

BNF表記と文脈自由文法の関係について

文脈自由文法

”文脈’の使い方に教えていただけませんか？

単語は文脈で覚えるべき？

文脈

例文集からの質問です。（よって文脈とかはありません）

多重文脈性とは…？

英語ってどういう言語ですか？

非断定的文脈と断定的文脈の違い 英語

文脈がわかりません

ｗｅｂを自由自在に操作しやすいプログラミング言語は

分数における「1」の意味は文脈によって変わる？

文脈自由文法をチョムスキー標準形に変換

環境的文脈効果（匂い）の記憶実験に自由再生課題を用いるわけを教えてくだ

文脈がわかりません

注目のQ&A

カテゴリ 一覧

専門家に質問してみよう 専門家登録

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

文脈自由言語についての質問です。よろしく　お願いします

非断定的文脈と断定的文脈の違い　英語

カテゴリ
一覧

専門家に質問してみよう
専門家登録