分野別過去問題テクノロジ系　情報に関する理論 No.3

情報に関する理論　(全37問中3問目)

No.3

次の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₀>

出典：平成29年秋期　問2

[この問題の出題歴]
応用情報技術者 H26春期問3
ソフトウェア開発技術者 H20秋期問7

分類

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

正解

ア

解説

各選択肢の文字列を問題中の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とわかります。

情報に関する理論 (全37問中3問目)

No.3

分類

正解

解説

情報に関する理論　(全37問中3問目)