応用情報技術者 試験情報＆徹底解説

各選択肢の文字列を問題中のBNFで表記すると次のようになります。

• 123→<R₁><R₂><R₀>
• 124→<R₁><R₂><R₁>
• 127→<R₁><R₂><R₁>
• 128→<R₁><R₂><R₂>

次に<A>の定義にある「<A><R₀>」「<B><R₂>」「<C><R₁>」の3つの型から導出されるBNFのパターンを考えます。

[<A> <R₀>]
非終端記号<A>に、それぞれ3つの型を当てはめます。

• <A><R₀><R₀>→<R₀><R₀><R₀>
• <B><R₂><R₀>→<R₁><R₂><R₀>
• <C><R₁><R₀>→<R₂><R₁><R₀>

[<B><R₂>]
非終端記号<B>に、それぞれ3つの型を当てはめます。

• <A><R₁><R₂>→<R₀><R₁><R₂>
• <B><R₀><R₂>→<R₁><R₀><R₂>
• <C><R₂><R₂>→<R₂><R₂><R₂>

[<C><R₁>]
非終端記号<C>に、それぞれ3つの型を当てはめます。

• <A><R₂><R₁>→<R₀><R₂><R₁>
• <B><R₁><R₁>→<R₁><R₁><R₁>
• <C><R₀><R₁>→<R₂><R₀><R₁>

上記の9つのBNFが非終端記号<A>で生成可能な文字列のパターンです。このうち選択肢の文字列と合致するのは「ア」123のBNF表記である「<R₁><R₂><R₀>」だけです。よって、<A>から生成可能な文字列は123とわかります。