情報に関する理論 (全53問中50問目)
No.50
終端記号の集合 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による導出として，正しいものはどれか。
出典：平成17年秋期 問8
- 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」と書換えされている部分が誤りです。