応用情報技術者 平成26年春期 午前問3についてはここでも質問・解答されていたので拝見したのですが、やっぱりよくわかりません。
https://www.virtualinvader.com/bnf-exam/
上記URLで解説を読んでいると
------------------------------------------------------
(ii) <A>が<A><R0>の場合
この時に「再帰」について考える必要があります。
<A>は、 <R0> か <A><R0> か <B><R2> か <C><R1> なので、以下に示すような可能性があります。
<R0><R0> か <A><R0><R0> か <B><R2><R0> か <C><R1><R0>
-----------------------------------------------------
まず、ここがなぜこのように変換あれるのかがよくわからないです。
つぎに
-----------------------------------------------------
また、問題文から、<A>は<R0>に、<B>は<R1>に、<C>は<R2>に置き換えられるということがわかります。
-----------------------------------------------------
なぜ置き換えられるのかがわかりません。
ここでずっと躓いています。
No.1
338
120
ええと、一致する文脈からすると正しいurlはこっちですよね？。
https://mi-chan-nel.com/backus-naur-form-introduction/
<R0> ::= 0 | 3 | 6 | 9
<R1> ::= 1 | 4 | 7
<R2> ::= 2 | 5 | 8
例文のようなこういう定義があった時、
<R0>は0または3または6または9の形を取り
<R1>は1または4または7の形を取り
<R2>は2または5または8の形を取る
となります。ここは意味を考えてはいけません。「出題者はそう定義した」のです。
そしてこれは、
0は<R0>でしか表現できず、
1は<R1>でしか表現できず、
2は<R2>でしか表現できず、
3は<R0>でしか表現できず、
4は<R1>でしか表現できず、
5は<R2>でしか表現できず、
6は<R0>でしか表現できず、
7は<R1>でしか表現できず、
8は<R2>でしか表現できず、
9は<R0>でしか表現できない事を意味します。
ここも意味を考えてはいけません。
上記の定義からは必然的にそういう結果とならざるを得ないからです。
ちょっと脱線して、選択肢の方を見てみましょう。
ア 123 イ 124 ウ 127 エ 128
アは <R1><R2><R0> という並びになった時にのみ表現可能です。
イは <R1><R2><R1> という並びになった時にのみ表現可能です。
ウは <R1><R2><R1> という並びになった時にのみ表現可能です。
エは <R1><R2><R2> という並びになった時にのみ表現可能です。
じゃあ<A>で表現できるのはア～エのうちのどれか、というのがこの問題というわけ。
-----------------------------------------------------
また、問題文から、<A>は<R0>に、<B>は<R1>に、<C>は<R2>に置き換えられるということがわかります。
-----------------------------------------------------
なぜ置き換えられるのかがわかりません。
今度は下の、一見すると難しそうな定義の方を見てみましょう。
<A> ::= <R0> | <A><R0> | <B><R2> | <C><R1>
<B> ::= <R1> | <A><R1> | <B><R0> | <C><R2>
<C> ::= <R2> | <A><R2> | <B><R1> | <C><R0>
余分な情報を削ぎ落としてみると次のようになります。
<A> ::= <R0>
<B> ::= <R1>
<C> ::= <R2>
<A>は<R0>の形を取る事が可能、
<B>は<R1>の形を取る事が可能、
<C>は<R2>の形を取る事が可能、というわけ。
なぜかって、出題者がそう定義したから（ここも頭で考えるところではない）。
あとurlの解説では、
(i) <A>が<R0>の場合
(ii) <A>が<A><R0>の場合
の2つしか考慮されていませんが、本当はここ、
(i) <A>が<R0>の場合
(ii) <A>が<A><R0>の場合
(iii) <A>が<B><R2>の場合
(iv) <A>が<C><R1>の場合
の4通りを考慮する必要があるはずなんですが、(iii)、(iv)を考慮するまでもなく(ii)で解に辿り着いてしまったため、(iii)、(iv)の解説を省略してしまっています。
以上を理解できたなら、残るは「再帰」という考え方のみです。
<A> ::= <R0> | <A><R0> | <B><R2> | <C><R1>
<A>が<A><R0>の場合、<A>の中に<A>が入っていますので、
ここでまた内側の<A>を展開する必要が出てきます。すると、
<A> → <A><R0> → <R0><R0>
<A> → <A><R0> → <A><R0><R0>
<A> → <A><R0> → <B><R2><R0>
<A> → <A><R0> → <C><R1><R0>
の4通りのいずれかになるわけ。
もしここで、<A><R0><R0>の<A>をまたまた<A><R0>として展開すると
<A><R0><R0> → <A><R0><R0><R0> → <A><R0><R0><R0><R0> …
のように無限に展開する事もできるんですが、
回答の選択肢は3桁なのでそこまで大きく展開する必要は無いですよね？
実はア～エの選択肢はいずれも「12?」の形なので、
「<R1><R2><R?>」のようになるケースを探せばいいだけだったりします。
<R1>は<B>の一形態ですから、ちょっと上に出てきた
<B><R2><R0>（<R1><R2><R0>）が求めるべき解であるというわけ。
そして<R1><R2><R0>となっているのはアしかありません。
2
1
2
1
1
0
補足：
結果が1桁になるケース（1通り）。
結果が2桁になるケース（3通り）。
結果が3桁となるケース（9通り）。
本当はこの9通り全てを書き出した上で、4つの選択肢と比較してみるべきなんだと思います。
なお、1桁が1通り、2桁が3通り、3桁が9通りという事は、
4桁は27通り、5桁は81通り、6桁は243通り…以下無限大(3n-1通り)
となっていそうな予感（さすがに検証するつもりはないけれど）。
あと、
<R1><R2><R1>（イ,ウ）
<R1><R2><R2>（エ）
のパターンがどこにも出てきませんでしたが、
のように、異なる始点でしか出現しないようです。