応用情報技術者 2014年 春期 午前2 問03

BNF導出の手順【午前2解説】

正解の理由

1. まず 〈A〉 を 〈A〉〈R_0〉 に展開して末尾に R0（ここでは "3" を選ぶ）を確保します。
   $⟨A⟩\Rightarrow ⟨A⟩⟨R_0⟩$
2. 次に左側の 〈A〉 を 〈B〉〈R_2〉 に展開して，左から2番目に R2 を置きます。
   $⟨A⟩⟨R_0⟩\Rightarrow ⟨B⟩⟨R_2⟩⟨R_0⟩$
3. さらにその 〈B〉 を 〈R_1〉 に展開して先頭に R1 を得ます。
   $⟨B⟩⟨R_2⟩⟨R_0⟩\Rightarrow ⟨R_1⟩⟨R_2⟩⟨R_0⟩$
4. 各 〈R_i〉 を具体的な端末記号に置き換えれば，例えば 〈R_1〉→1, 〈R_2〉→2, 〈R_0〉→3 として「123」が得られます。
   以上で 〈A〉 ⇒* 1 2 3 となり，選択肢アは生成されます。

解法ステップ

1. 各記号群の端末集合を確認：〈R_0〉={0,3,6,9}, 〈R_1〉={1,4,7}, 〈R_2〉={2,5,8}。
2. 問題の文字列の各桁がどの 〈R_i〉 に属するかを対応付ける（例: 123 → R1 R2 R0）。
3. そのクラス列を得るために，文法規則でどの順序・どの非終端を展開すればよいかを考える。
   • 末尾が R0 なら〈A〉→〈A〉〈R_0〉を使うのが自然（末尾を固定）。
   • 残りを左側の 〈A〉 部分で作ればよい。
4. 実際に導出を行い（上記「正解の理由」を参照）、端末記号に置き換えて照合する。
5. 必要ならば同様の手順で他の候補も試し，生成可否を列挙する。

選択肢別の誤答解説

• ア（123）
  先に示した通り生成可能。導出の順序は $⟨A⟩\Rightarrow ⟨A⟩⟨R_0⟩\Rightarrow ⟨B⟩⟨R_2⟩⟨R_0⟩\Rightarrow ⟨R_1⟩⟨R_2⟩⟨R_0⟩$ と進めます。
• イ（124）・ウ（127）
  どちらもクラス列としては R1 R2 R1 に対応します。これらは次のように生成できます：
  $⟨A⟩\Rightarrow ⟨C⟩⟨R_1⟩\Rightarrow ⟨B⟩⟨R_2⟩⟨R_1⟩\Rightarrow ⟨R_1⟩⟨R_2⟩⟨R_1⟩$
  あとは各 〈R_i〉 を具体的に選べば（先頭の R1→1, 中央の R2→2, 終端の R1→4 または 7 等）「124」や「127」が得られます。したがってこれらも〈A〉から生成可能です。
• エ（128）
  クラス列は R1 R2 R2 になりますが，上で列挙した長さ3の可能なクラス列（下節参照）には R1 R2 R2 が含まれません。総当たりで導出パターンを調べると，〈A〉から長さ3の文字列として生成できるクラス列は次の9通りに限られます：
  • A→A R0 系： R0 R0 R0、R1 R2 R0、R2 R1 R0
  • A→B R2 系： R0 R1 R2、R1 R0 R2、R2 R2 R2
  • A→C R1 系： R0 R2 R1、R1 R2 R1、R2 R0 R1
    上記に R1 R2 R2（= 1 2 8）は含まれないため，128 は〈A〉から生成できません。

よくある誤解

• 導出の適用順序を雑に書く（前回の誤り）。例えば「〈A〉→〈B〉〈R_2〉の形で…さらに〈A〉が '3' を生成」といった順序逆転は誤りです。正しい導出順序を左から順に（または右から順に）明確に書くこと。
• 〈R_i〉 を単一の記号と見なして交互作用を無視する。〈R_0〉等は複数の端末を含み，「どの具体的端末を選べるか」を意識すること。
• 「非終端記号の名前＝最後に出るクラス」と誤解すること。文法は相互再帰しており，非終端の展開によって最後のクラスは変わり得ます。

補足コラム

# 深さ制限付きの単純な導出探索（擬似実装）
rules = {
  'A': [['R0'], ['A','R0'], ['B','R2'], ['C','R1']],
  'B': [['R1'], ['A','R1'], ['B','R0'], ['C','R2']],
  'C': [['R2'], ['A','R2'], ['B','R2'], ['C','R0']],
  'R0': [['0'],['3'],['6'],['9']],
  'R1': [['1'],['4'],['7']],
  'R2': [['2'],['5'],['8']],
}
# 幅優先で導出列を展開し，目標文字列が得られるかを判定することができます。

FAQ