問題プレビューID: 9aee0fbe応用情報技術者試験 2017年(平成29年度)秋期 午前

問 2
応用情報技術者試験 2017年(平成29年度)秋期 午前

次の 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⟩
解説

正解は「ア」です。

非終端記号 ⟨R0⟩ は {0, 3, 6, 9},⟨R1⟩ は {1, 4, 7},⟨R2⟩ は {2, 5, 8} という 1 文字を生成します。⟨A⟩,⟨B⟩,⟨C⟩ はこれらの連結として 2 文字以上の文字列を生成します。

  • ア(123): まず ⟨B⟩ を ⟨R1⟩ で展開すると「1」が得られます。次に ⟨A⟩ を ⟨B⟩⟨R2⟩ で展開すると「1」+⟨R2⟩ となり,⟨R2⟩ を 2 として「12」が得られます。さらに ⟨A⟩ を ⟨A⟩⟨R0⟩ で展開すると「12」+⟨R0⟩ となり,⟨R0⟩ を 3 として「123」が生成できます。正しい。
  • イ(124): 1 と 2 は生成できますが,末尾の 4 は ⟨R1⟩ の要素であり,⟨A⟩ の規則では ⟨R1⟩ を末尾に連結する規則がないため生成できません。
  • ウ(127): 末尾の 7 は ⟨R1⟩ の要素であり,⟨A⟩ から生成できる末尾の要素(⟨R0⟩,⟨R2⟩,⟨R1⟩ のいずれか)の組合せと一致しません。
  • エ(128): 末尾の 8 は ⟨R2⟩ の要素であり,⟨A⟩ の生成規則では末尾に ⟨R2⟩ を連結する規則がないため生成できません。

関連問題

本文が同じ・似ている問題を表示しています