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

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

<R0> ::= 0|3|6|9
<R1> ::= 1|4|7
<R2> ::= 2|5|8
<A> ::= <R0>|<A> <R0>|<B> <R2>|<C>< R1>
<B> ::= <R1>|<A> <R1>|<B> <R0>|<C>< R2>
<C> ::= <R2>|<A> <R2>|<B> <R1>|<C> <R0>

  • 123
  • 124
  • 127
  • 128
正解 問題へ
分野:テクノロジ系
中分類:基礎理論
小分類:情報に関する理論
解説
各選択肢の文字列を問題中のBNFで表記すると次のようになります。
  • 123→<R1><R2><R0>
  • 124→<R1><R2><R1>
  • 127→<R1><R2><R1>
  • 128→<R1><R2><R2>
次に<A>の定義にある「<A><R0>」「<B><R2>」「<C><R1>」の3つの型から導出されるBNFのパターンを考えます。

[<A> <R0>]
非終端記号<A>に、それぞれ3つの型を当てはめます。
  • <A><R0><R0>→<R0><R0><R0>
  • <B><R2><R0>→<R1><R2><R0>
  • <C><R1><R0>→<R2><R1><R0>
[<B><R2>]
非終端記号<B>に、それぞれ3つの型を当てはめます。
  • <A><R1><R2>→<R0><R1><R2>
  • <B><R0><R2>→<R1><R0><R2>
  • <C><R2><R2>→<R2><R2><R2>
[<C><R1>]
非終端記号<C>に、それぞれ3つの型を当てはめます。
  • <A><R2><R1>→<R0><R2><R1>
  • <B><R1><R1>→<R1><R1><R1>
  • <C><R0><R1>→<R2><R0><R1>
上記の9つのBNFが非終端記号<A>で生成可能な文字列のパターンです。このうち選択肢の文字列と合致するのは「ア」123のBNF表記である「<R1><R2><R0>」だけです。よって、<A>から生成可能な文字列は123とわかります。

この問題の出題歴


Pagetop