AP | 有限オートマトン②

前回は有限オートマトンについて解説しました。

今回は別形式の問題を解いてみましょう！

問題

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



ア　1011　イ　1100　ウ　1101　エ　1110

 (平成21年春季試験)

解き方

順番に入力していきましょう。

S3で受理状態となるため、最後がS3で終わらなければいけません。

ア　1 ⇒ 0 ⇒ 1 ⇒ 1

S1 ⇒ 1 ⇒ S2 ⇒ 0 ⇒ S2 ⇒ 1 ⇒ S1 ⇒ 1 ⇒ S2 　➡不受理

イ　1 ⇒ 1 ⇒ 0 ⇒ 0

S1 ⇒ 1 ⇒ S2 ⇒ 1 ⇒ S1 ⇒ 0 ⇒ S3 ⇒ 0 ⇒ S2 　➡不受理

ウ　1 ⇒ 1 ⇒ 0 ⇒ 1

S1 ⇒ 1 ⇒ S2 ⇒ 1 ⇒ S1 ⇒ 0 ⇒ S3 ⇒ 1 ⇒ S3 　➡受理

エ　1 ⇒ 1 ⇒ 1 ⇒ 0

S1 ⇒ 1 ⇒ S2 ⇒ 1 ⇒ S1 ⇒ 1 ⇒ S2 ⇒ 0 ⇒ S2　 ➡不受理

以上より、正解はウとなります。

次回も、有限オートマトンの問題を解いてみましょう。