BNF記法に関する問題の考え方を教えて下さい。


下記は2つとも同じ問題の解説です。
ttp://www.ap-siken.com/kakomon/20_aki/q7.html
ttp://learning.zealseeds.com/contents/ProblemAndExplanation/IPA/AP/AP20B/07/index.html

どちらも解説を何度も読みましたが途中から理解不能です。
(2番目のリンクでいくと、 「4.ここまでの12に該当するのは<A>=<B><R2>のみです。」というところからついていけてません )

使用されている記号の意味や、"再帰的に読むべし"というルールまでは理解しているつもりですが、上記問題がわからないので、何か肝心なところを理解できてない気がします。

ちなみに下記の問題は理解できます。
ttp://www.ap-siken.com/kakomon/24_haru/q3.html
(これは文字数から判断できるので少し性質が違う問題かもしれませんが...)

上の方の問題に対して、少し詳しめの解説をお願い致します。

回答の条件
  • 1人3回まで
  • 登録:2015/09/22 11:52:25
  • 終了:2015/09/22 17:40:45

ベストアンサー

id:pmint No.3

pmint回答回数41ベストアンサー獲得回数62015/09/22 14:46:18スマートフォンから投稿

ポイント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のみ生成可能)

続くほど左に数字が増えていく定義になっています。
また、再帰的に続く場合と、終端(左端の文字)が一緒くたに定義されているため、より分かりにくくなっています。
f:id:pmint:20150922150720p:image

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だけが生成可能だと分かります。
id:kon39392

ありとうございます。
どの回答もわかりやすかったですが、理解力のない私がピンとくるきっかけを与えてくださったのでベストアンサーとさせてください。

ありがとうございました。

2015/09/22 17:39:24

その他の回答(2件)

id:Mook No.1

Mook回答回数1312ベストアンサー獲得回数3912015/09/22 13:04:42

ポイント65pt

二つの回答は攻める方向が逆ですが、どちらでやるのがやりやすいか、ご自身で確認して見てください。

解説の二番煎じですが、下の方の回答(元の数字から<A> に辿っていく)の方法で考えてみると、

回答群のすべてが12# で、最初の二つの数字はすでに確定していますから、
この始めの二桁の形は

<R1> <R2>
です。<R1>は終端<B>なので

<B> <R2>  =>  <A>
の形です。

初めの2桁が<A>の三桁の数値を生成するのは
<A> <R0>  =>  <A>
<A> <R1>  =>  <B>
<A> <R2>  =>  <C>
ですが、<A> から生成されるのですから、

<A> ::= <A> <R0>
の形で、最終桁は<R0> とわかります。回答群の中で、末尾が R0 に含まれるのは 3 だけなので
回答は [ア] になります。

上の回答は<A> から数字に分解して一致するかを確認しているので、考える方向が逆になっていますが
どちらでも回答は一緒になります。
id:jan8 No.2

jan8回答回数455ベストアンサー獲得回数962015/09/22 13:47:26

ポイント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>しかありません。

id:pmint No.3

pmint回答回数41ベストアンサー獲得回数62015/09/22 14:46:18スマートフォンから投稿ここでベストアンサー

ポイント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のみ生成可能)

続くほど左に数字が増えていく定義になっています。
また、再帰的に続く場合と、終端(左端の文字)が一緒くたに定義されているため、より分かりにくくなっています。
f:id:pmint:20150922150720p:image

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だけが生成可能だと分かります。
id:kon39392

ありとうございます。
どの回答もわかりやすかったですが、理解力のない私がピンとくるきっかけを与えてくださったのでベストアンサーとさせてください。

ありがとうございました。

2015/09/22 17:39:24

コメントはまだありません

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません