AP | 有限オートマトン②

2019年3月20日水曜日

応用情報技術者試験

t f B! P L
前回は有限オートマトンについて解説しました。

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

問題


次に示す有限オートマトンが受理する入力列はどれか。ここでは,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  ➡不受理

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

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

QooQ