ソフトウェア開発技術者平成17年秋期 午前問8

問8

終端記号の集合 T={0,1},非終端記号の集合 N={A,B,C,S},及び書換え規則の集合
 P={S→ε,S→0A,S→1B,A→0S,A→1C,B→1S,B→0C,C→1A,C→0B}
を考える。ここで,εは空列を表す記号とする。
 G=(T,N,P,S)
で定義される文法Gによる導出として,正しいものはどれか。
  • S⇒0A⇒00C⇒000A⇒0000S⇒0000
  • S⇒0A⇒01C⇒011B⇒0111S⇒0111
  • S⇒1B⇒10C⇒101A⇒1010S⇒1010
  • S⇒1B⇒10C⇒101A⇒1011S⇒1011

分類

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

正解

解説

規則の集合で定義されている以下の方法だけを用いて変換しているものが正解となります。
08.gif/image-size:345×59
  • 2つ目の変換で「A→0C」と書換えされている部分が誤りです。
  • 3つ目の変換で「C→1B」と書換えされている部分が誤りです。
  • 正しい。全ての書換えが規則に従って行われています。
  • 5つ目の変換で「A→1S」と書換えされている部分が誤りです。
© 2010-2024 応用情報技術者試験ドットコム All Rights Reserved.

Pagetop