次のBNFにおいて非終端記号Aから生成される文字列はどれか。

【問題】

R₀ = 0 | 3 | 6 | 9

R₁ = 1 | 4 | 7

R₂ = 2 | 5 | 8

A ::= <R₀> | <A><R₀> | <R₂> | <C><R₁>

B ::= <R₁> | <A><R₁> | <R₀> | <C><R₂>

C ::= <R₂> | <A><R₂> | <R₁> | <C><R₀>

ア．123　イ．124　ウ．127　エ．128

【解答】

「12」から始まり、なおかつ生成できる文字列を考えれば良い。

とすると、1はR₁であり、２はR₂である必要があるから、<R₁><R₂>は必須になる。

さらに3文字であるから、<R₁><R₂><R_x>と考えられる。

さらに、「Aから生成される」とあるから、順に考えると、

A　→　<A><R₀>　は

<A><R₀>　→　<R₂><R₀>　のみが考えられ、

<R₂><R₀>　→　<R₁><R₂><R₀>　のみが考えられる。

よって、作られるのは、「120」「123」「126」「129」のどれかであり、満たすのはアのみである。

なお、A　→　<R2>　を考えると、

<R₂>　→　<C><R₂><R₂>　→　<R₂><R₂><R₂>　のみが考えられるが、<R₁><R₂><R_x>を生成できないため、不適切となる。

同様に、A　→　<C><R₁>　を考えると、

<C><R₁>　→　<A><R₂><R₁>　→　<R₀><R₂><R₁>　のみが考えられるが、やはり<R₁><R₂><R_x>を生成できないため、不適切となる。