平成21年度 春期 応用情報技術者試験 午前 問3
テクノロジ／基礎理論次に示す有限オートマトンが受理する入力列はどれか。ここで，S1 は初期状態を，S3 は受理状態を表している。
出典：平成21年度 春期 応用情報技術者試験 午前 問3
- ア1011
- イ1100
- ウ1101
- エ1110
正解：ウ
解説
図の状態遷移は，S1が入力1でS2へ，S2が入力1でS1へ，S1が入力0でS3へ，S3が入力0でS2へ，S2は入力0で自己ループ，S3は入力1で自己ループします。入力列「1101」を左から読むと，S1→(1)S2→(1)S1→(0)S3→(1)S3となり，受理状態S3で終わるため受理されます。
選択肢ごとの解説
- ア誤り。「1011」はS1→S2→(0で自己ループ)S2→(1)S1→(1)S2となり，S2で終わるため受理されません。
- イ誤り。「1100」はS1→S2→S1→(0)S3→(0)S2となり，S2で終わるため受理されません。
- ウ正しい。「1101」はS1→S2→S1→S3→(自己ループ1)S3となり，受理状態S3で終わります。
- エ誤り。「1110」はS1→S2→S1→S2→(自己ループ0)S2となり，S2で終わるため受理されません。