- 締切済み
文脈自由言語についての質問です。よろしく お願いします
文脈自由言語についての質問です。よろしく お願いします
- chujunshi
- お礼率24% (9/37)
- ハードウェア・サーバー
- 回答数1
- ありがとう数1
- みんなの回答 （1）
- 専門家の回答
みんなの回答
- Tacosan
- ベストアンサー率23% (3656/15482)
ぶっちゃけどこが「ハードウェア (サーバ)」なのか皆目見当がつかないのだが, 例えば L = { w^R w | w ∈ { 0, 1 }^* } ならできるか?
関連する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点につきまして、ご回答よろしくお願いいたします。
- 締切済み
- その他（学問・教育）
- ”文脈’の使い方に教えていただけませんか？
みなさん、はじめまして＾＾ ”文脈’という単語は、辞書そう書いてありますが： ぶん-みゃく [0] 【文脈】 （１）文における個々の語または個々の文の間の論理的な関係・続き具合。文の脈絡。コンテクスト。「前後の―から意味を判断する」 （２）一般に，すじみち・脈絡。また，ある事柄の背景や周辺の状況。 私はある友達と下記ような対話をしましたが。。。。 友達：”うまい”の意味は何ですか？ 私：”delicious"です。 友達：そうですか、でもそんな翻訳は私の場合にはふさわしくないと思いますが。 私：文脈は？ 友達：”文脈”？どういう意味？ 。。。。。。。。。 私は”文脈は”と言ったのは、つまり文脈を見てから、その場合にふさわしい翻訳をできるということですが、どうして友達はわからないですか。私はどこか間違えていたのか？ 教えてください、どうも＾＾
- ベストアンサー
- 日本語・現代文・国語
- 単語は文脈で覚えるべき？
単語は文脈で覚えるべき？ こんにちは、このカテでも どうやったら英単語を効率よく覚えられるかという質問が出されます。そして、文脈で覚えたほうがいいという意見もよく聞きます。私は中学、高校と英単語は比較的すらすら覚えられましたので、単語で苦労した思い出はあまりないのですが、必ずしも単語は文脈で覚えるのが正しいのか疑問を感じるようになりました。というのは、私はスペイン語を勉強しているのですが、文脈に頼った覚え方だと 出会ったことのある単語でも 文脈が違ってくると 度忘れしたように意味がピンと浮かんでこなかったり、特に作文なんかをする時に、単語があやふやだったりすることが往々にしてあります。そこで質問です。単語をおぼえるには、やはり単語だけを個別に一つずつ潰していくことも大事ではないでしょうか？
- ベストアンサー
- 英語
お礼
ありがとうございます