今回は別形式の問題を解いてみましょう!
問題
次に示す有限オートマトンが受理する入力列はどれか。ここでは,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 ➡不受理
以上より、正解はウとなります。
次回も、有限オートマトンの問題を解いてみましょう。
0 件のコメント:
コメントを投稿