平成29年 秋期 応用情報技術者 午前 問2

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


答え ア


解説

 ア  生成される文字列が“123”となるのは、『<R1><R2><R0>』となることであり、これは
<B> = <R1>
<A> = <B><R2>
<A> = <A><R0>
のときであり、<A>から生成される。
 イ  生成される文字列が“124”となるのは、『<R1><R2><R1>』となることであり、これは
<B> = <R1>
<A> = <B><R2>
<B> = <A><R1>
のときであり、<B>から生成される。
 ウ  生成される文字列が“127”となるのは、『<R1><R2><R1>』となることであり、これは
<B> = <R1>
<A> = <B><R2>
<B> = <A><R1>
のときであり、<B>から生成される。
 エ  生成される文字列が“128”となるのは、『<R1><R2><R2>』となることであり、これは
<B> = <R1>
<A> = <B><R2>
<C> = <A><R2>
のときであり、<C>から生成される。


キーワード
・BNF

キーワードの解説
  • BNF(Backus Naur Form、バッカス記法、バッカス・ナウア記法)
    コンピュータで扱う言語を定義するための記述方法(メタ言語の記述方法)であり、メタ言語の多くはBNFで記述される。
    マークアップ言語として使われるXMLも、BNFで定義されている。
    問題の「<R0>::= 0 | 3 | 6 | 9」は<R0>が“0”か“3”か“6”か“9”のいずれかであることを意味しています。

もっと、「BNF」について調べてみよう。

戻る 一覧へ 次へ