平成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による導出として，正しいものはどれか。
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
広告
解説
規則の集合で定義されている以下の方法だけを用いて変換しているものが正解となります。
- 2つ目の変換で「A→0C」と書換えされている部分が誤りです。
- 3つ目の変換で「C→1B」と書換えされている部分が誤りです。
- 正しい。全ての書換えが規則に従って行われています。
- 5つ目の変換で「A→1S」と書換えされている部分が誤りです。
広告