下記は２つとも同じ問題の解説です。
ttp://www.ap-siken.com/kakomon/20_aki/q7.html
ttp://learning.zealseeds.com/contents/ProblemAndExplanation/IPA/AP/AP20B/07/index.html
どちらも解説を何度も読みましたが途中から理解不能です。
（２番目のリンクでいくと、 「4．ここまでの12に該当するのは<A>=<B><R2>のみです。」というところからついていけてません ）
使用されている記号の意味や、"再帰的に読むべし"というルールまでは理解しているつもりですが、上記問題がわからないので、何か肝心なところを理解できてない気がします。
ちなみに下記の問題は理解できます。
ttp://www.ap-siken.com/kakomon/24_haru/q3.html
（これは文字数から判断できるので少し性質が違う問題かもしれませんが...）
上の方の問題に対して、少し詳しめの解説をお願い致します。
No.3
41
6
70pt
表記順序が分かりにくいんだと思います。
簡略化して
R0 ::= 3 A ::= R0｜A R0
これだとAからは3、33、333…が生成可能です。
次に
R0 ::= 3 R1 ::= 1 A ::= R0｜A R0｜B R0 B ::= R1
これならAからは3、3 3、3 3 3…のほか、1 3も生成可能になります。（Bからは1のみ生成可能）
続くほど左に数字が増えていく定義になっています。
また、再帰的に続く場合と、終端（左端の文字）が一緒くたに定義されているため、より分かりにくくなっています。
2つのリンク先ではどちらも<R0> <R1> <R2>に置き換えて統一することで、考えやすくしているようです。
これを踏まえて、2番目のリンク先を補足するとこんな感じでしょうか。
（解説1、2、3は省略） 4. ここまでで1 2という文字列に該当するのは<A>のみです。そして<A>はBNFにある通り、<B><R2>と置換可能です。 5. 問題文より<A>から生成できる文字列さえ考えればいいのですが、 非終端記号である<A>から1 2を生成する例は… <A> = <A><R0> （BNFより。以下も同様） = <B><R2><R0> （<A>部分を解説4に基づいて置き換えた結果） = <R1><R2><R0> （<B>を分かりやすく置換） …しか該当しません。 これが<A>から生成可能で、左端が1 2で「終わる」例を探した結果です。 5.5. ここで、1番目のリンク先にある解説から <R1><R2><R0> を探してみてください。 6. [ア]の123だけが生成可能だと分かります。
No.1
1314393
65pt
二つの回答は攻める方向が逆ですが、どちらでやるのがやりやすいか、ご自身で確認して見てください。
解説の二番煎じですが、下の方の回答（元の数字から<A> に辿っていく）の方法で考えてみると、 回答群のすべてが12# で、最初の二つの数字はすでに確定していますから、 この始めの二桁の形は <R1> <R2> です。<R1>は終端<B>なので <B> <R2> => <A> の形です。 初めの２桁が<A>の三桁の数値を生成するのは <A> <R0> => <A> <A> <R1> => <B> <A> <R2> => <C> ですが、<A> から生成されるのですから、 <A> ::= <A> <R0> の形で、最終桁は<R0> とわかります。回答群の中で、末尾が R0 に含まれるのは 3 だけなので 回答は [ア] になります。 上の回答は<A> から数字に分解して一致するかを確認しているので、考える方向が逆になっていますが どちらでも回答は一緒になります。
No.2
45696
65pt
ちょっと複雑なだけですよ
例えばBNFの規則に従って、
<A>::=<R0>⇒6
<B>::=<R1>⇒7
<C>::=<R2>⇒8
<A>::=<A><R0>⇒63
<B>::=<A><R1>⇒637
<C>::=<B><R1>⇒6374
<B>::=<C><R2>⇒63748
<A>::=<B><R2>⇒637488
<A>::=<A><R0>⇒6374883
などと、文字列をずーっと生成する事が出来ます。
これは、
<A>
=<A><R0>
=<B><R2><R0>
=<C><R2><R2><R0>
=<B><R1><R2><R2><R0>
=<A><R1><R1><R2><R2><R0>
=<A><R0><R1><R1><R2><R2><R0>
=<R0><R0><R1><R1><R2><R2><R0>
=6374883
と表す事が出来ます。
問題文は「<A>は123,124,127,128の内どれか？」と聞いています。
123,124,127,128を<A>から生成しようとすると、
<B>::=<R1>⇒1
<A>::=<B><R2>⇒12
<A>::=<A><R0>⇒120 または 123 または 126 または 129
となるので、<A>になるのは123しかありません。
「4．ここまでの12に該当するのは<A>=<B><R2>のみです。」の解説
<A><B><C>のBNF記法をよく見ると、ほとんどが2文字の組み合わせになっており、1文字単独で構成できるのは、
<A>::=<R0>
<B>::=<R1>
<C>::=<R2>
の3つしかありません。
従って、1は、<B>=<R1>しかありません。
続いて、12は、<A>::=<B><R2>=<R1><R2>しかありません。
No.3
416
ここでベストアンサー
70pt
表記順序が分かりにくいんだと思います。
簡略化して
R0 ::= 3 A ::= R0｜A R0
これだとAからは3、33、333…が生成可能です。
次に
R0 ::= 3 R1 ::= 1 A ::= R0｜A R0｜B R0 B ::= R1
これならAからは3、3 3、3 3 3…のほか、1 3も生成可能になります。（Bからは1のみ生成可能）
続くほど左に数字が増えていく定義になっています。
また、再帰的に続く場合と、終端（左端の文字）が一緒くたに定義されているため、より分かりにくくなっています。
2つのリンク先ではどちらも<R0> <R1> <R2>に置き換えて統一することで、考えやすくしているようです。
これを踏まえて、2番目のリンク先を補足するとこんな感じでしょうか。
（解説1、2、3は省略） 4. ここまでで1 2という文字列に該当するのは<A>のみです。そして<A>はBNFにある通り、<B><R2>と置換可能です。 5. 問題文より<A>から生成できる文字列さえ考えればいいのですが、 非終端記号である<A>から1 2を生成する例は… <A> = <A><R0> （BNFより。以下も同様） = <B><R2><R0> （<A>部分を解説4に基づいて置き換えた結果） = <R1><R2><R0> （<B>を分かりやすく置換） …しか該当しません。 これが<A>から生成可能で、左端が1 2で「終わる」例を探した結果です。 5.5. ここで、1番目のリンク先にある解説から <R1><R2><R0> を探してみてください。 6. [ア]の123だけが生成可能だと分かります。
ありとうございます。
どの回答もわかりやすかったですが、理解力のない私がピンとくるきっかけを与えてくださったのでベストアンサーとさせてください。
ありがとうございました。
1
1
1
1
1
43
42
ありとうございます。
2015/09/22 17:39:24どの回答もわかりやすかったですが、理解力のない私がピンとくるきっかけを与えてくださったのでベストアンサーとさせてください。
ありがとうございました。