平成20年秋期試験問題 午前問7

平成20年秋期試験問題　午前問7

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

<R₀> ::= 0｜3｜6｜9
<R₁> ::= 1｜4｜7
<R₂> ::= 2｜5｜8
<A> ::= <R₀>｜<A> <R₀>｜ <R₂>｜<C>< R₁>
 ::= <R₁>｜<A> <R₁>｜ <R₀>｜<C>< R₂>
<C> ::= <R₂>｜<A> <R₂>｜ <R₁>｜<C> <R₀>

正解　ア問題へ

分野：テクノロジ系
中分類：基礎理論
小分類：情報に関する理論

解説

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

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

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

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

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

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

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

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

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

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