応用情報技術者平成26年春期 午前問3

問3

次の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
  • [出題歴]
  • 応用情報技術者 H29秋期 問2
  • ソフトウェア開発技術者 H20秋期 問7

分類

テクノロジ系 » 基礎理論 » 情報に関する理論

正解

解説

各選択肢の文字列を問題中の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とわかります。
© 2010-2024 応用情報技術者試験ドットコム All Rights Reserved.

Pagetop