平成２１年春期高度情報技術者試験問題　問２：有限オートマトン

平成２１年度春期高度情報技術者試験問題と解説

次に示す有限オートマトンが受理する入力列はどれか。ここで、Ｓ₁は初期状態を、Ｓ₃は受理状態を表している。

ア　1011

イ　1100

ウ　1101

エ　1110

ウ

以下のとおり、遷移する。

ア　Ｓ₁ → 1 → Ｓ₂ → 0 → Ｓ₂ → 1 → Ｓ₁ → 1 → Ｓ₂ となり、受理しない。

イ　Ｓ₁ → 1 → Ｓ₂ → 1 → Ｓ₁ → 0 → Ｓ₃ → 0 → Ｓ₂ となり、受理しない。

ウ　正しい。Ｓ₁ → 1 → Ｓ₂ → 1 → Ｓ₁ → 0 → Ｓ₃ → 1 → Ｓ₃ となり、受理する。

エ　Ｓ₁ → 1 → Ｓ₂ → 1 → Ｓ₁ → 1 → Ｓ₂ → 0 → Ｓ₂ となり、受理しない。