文脈自由文法

質問

・　<assugn>::=<id>=<expr>
・ <id>::=A|B|C
・　<expr>::=<expr>+<expr>|<expr>*<expr>|(<expr>)|<id>

問題
Ａ＝Ｂ＋Ｃ＊Ａの式を使って、上記文脈自由文法が「曖昧」であることを証明しなさい。

この問題を解答できる方がいましたら宜しくお願いします。

また合わせて解説していただけると大変助かります。

Ａ，Ｂ，Ｃの式というのが何を指しているのかも分からない状態です。

すみません、宜しくお願いします。

回答No.3

kmee

こんなものは、答えだけ聞いてもなんの役にも立ちません
ちょっと変えただけでまったく別の結論になることだってあります。
「この文法を曖昧さが無くなるように変更せよ」という応用問題へと継げるのは当然の流れでしょう。

既に指摘のあるとおり、まずは、基礎を勉強してからにしましょう。

<id>とか<expr>とかは、ただの名前です。他と区別するために記号を付けただけです。
　<味噌汁>::=<じゃがいも>=<みかん>
　<じゃがいも>::=A|B|C
　<みかん>::=<みかん>+<みかん>|<みかん>*<みかん>|(<みかん>)|<じゃがいも>
でも、文法は同じです。
ただ、これだとわけがわからないので、文脈での役割に沿った、意味をある名前を付けているのです。

お礼

まるほど、応用問題への発想を教えていただきありがとうございました。
ただの名前だったのですね！！

回答No.2

hpsg

単純化して書きます。正確には講義ノートとか教科書参考書で把握すべき内容です。

「assign」はそのまま英単語です。
「割り当てる」等の意味で、最近は日本語でも「作業AにX君をアサインする」などと使う場面があります。

「id」　英単語 identifier の略ですが日本語でも使うでしょう。
たとえば学生証みたいなメンバー認証の役割を含むカードをIDカードと呼ぶ、そのIDです。
この文法では登録メンバーはA,B,Cの三記号（だけ）ですね。

「::=」　図的記号『⇒』の代わりと思うのが一番簡単。⇒の左を生成する規則は矢印の右だ、です。

お礼

。⇒の左を生成する規則は矢印の右だ、です。

(上)大変理解することができました。ありがとうございました

回答No.1

hpsg

「Ａ，Ｂ，Ｃの式というのが何を指しているのかも分からない」なんて状態で、『文法が曖昧であること』はわかっているのでしょうか？
また、解析木のような用語とか。予備知識を全部書くことは、この問題を出題した教員の講義あるいはこの問題が載っていた書籍を全部再現しなければならないので「解説する」作業はは現実的ではありません。

簡単には、右辺が（Ｂ＋Ｃ）×Ａ　という解釈になるか　Ｂ＋（Ｃ×Ａ）　という解釈になるか、与えられたルールでは決まらないぞと主張すれば良いでしょう。

お礼

はい、hpsgさんの仰る通りで、予備知識があまりにも不足しているために
一文字の解答もできない状態です。

「文法が曖昧であること」の意味は調べて、文法上正しい構造を複数持つ　
ということだと分かりました。

（Ｂ＋Ｃ）×Ａ　という解釈になるか　Ｂ＋（Ｃ×Ａ）ですね・・・
ＢとかＣというのは何のことなのでしょうか😢

補足

assugnはassignの間違えでしたすみません。

「assign」「id」 「::=」はどういった意味なのでしょうか。。。
「exrr」は「expression」のことかなと思っています。