平成29年 秋期 問2
広告
ツナさん
(No.1)
解説の最後に
とありますが、何故選択肢の文字列と合致するのは「<R1><R2><R0>」だけなのでしょうか。
何度計算しても調べてみても分からなかったので、ご教示をお願いします。
>上記の9つのBNFが非終端記号<A>で生成可能な文字列のパターンです。このうち選択肢の文字列と合致するのは〔イ〕123のBNF表記である「<R1><R2><R0>」だけです。よって、<A>から生成可能な文字列は123とわかります。
とありますが、何故選択肢の文字列と合致するのは「<R1><R2><R0>」だけなのでしょうか。
何度計算しても調べてみても分からなかったので、ご教示をお願いします。
2023.07.30 14:59
まーぼさん
(No.2)
https://www.ap-siken.com/s/kakomon/29_aki/q2.html
非終端記号<A>から生成可能な文字列はたくさんあるので選択肢から逆算した方が速いです。
アの123になるためには1,2,3はそれぞれ<R1>,<R2
<A> →...→<R1><R2><R0>→…→123
BNFを見ると、右に伸びる生成規則がないので、
<A>に適用する規則は<R0>が一番右に来ている規則を適用します。
<A> → <A><R0>→…→<R1><R2><R0>→…→123
<R0>の左には<R2>が来ているので<R2>が右端に来る生成規則を適用します。
<A> → <A><R0> → <B><R2><R0>→…<R1><R2><R0>→...→123
あとは<B>を<R1>にする規則を適用すればいいので、
<A> → <A><R0> → <B><R2><R0>→<R1><R2><R0>→123
<A>から123が導出できることが分かります。
他の選択肢も同様に逆からやってみると導出できない部分がでてくるはずです。
非終端記号<A>から生成可能な文字列はたくさんあるので選択肢から逆算した方が速いです。
アの123になるためには1,2,3はそれぞれ<R1>,<R2
>,<R0>からしか導出できないので<R1><R2><R0>を経由しなければなりません。
<A> →...→<R1><R2><R0>→…→123
BNFを見ると、右に伸びる生成規則がないので、
<A>に適用する規則は<R0>が一番右に来ている規則を適用します。
<A> → <A><R0>→…→<R1><R2><R0>→…→123
<R0>の左には<R2>が来ているので<R2>が右端に来る生成規則を適用します。
<A> → <A><R0> → <B><R2><R0>→…<R1><R2><R0>→...→123
あとは<B>を<R1>にする規則を適用すればいいので、
<A> → <A><R0> → <B><R2><R0>→<R1><R2><R0>→123
<A>から123が導出できることが分かります。
他の選択肢も同様に逆からやってみると導出できない部分がでてくるはずです。
2023.07.30 16:00
ツナさん
(No.3)
そういうことだったんですね!
やっと分かりました。ご回答ありがとうございました。
やっと分かりました。ご回答ありがとうございました。
2023.07.30 16:21
返信投稿用フォーム
スパム防止のためにスレッド作成日から30日経過したスレッドへの投稿はできません。