平成21年度春期 応用情報技術者試験 午前 問3

正解：ウ

AI解説

状態遷移図をS1（初期状態）から入力列に従ってたどり、最終的にS3（受理状態）に到達するかどうかで受理・不受理を判定する。設問の遷移規則（S1:1→S2,0→S3／S2:1→S1,0→S2／S3:1→S3,0→S2）に基づき順にたどると、「1101」だけがS1→S2→S1→S3→S3と遷移し、最終状態がS3になる。 ア: 「1011」はS1→S2→S2→S1→S2とたどり、最終状態がS2となるため受理されない。 イ: 「1100」はS1→S2→S1→S3→S2とたどり、最終状態がS2となるため受理されない。 ウ: 「1101」はS1→S2→S1→S3→S3とたどり、最終状態が受理状態S3となるため受理される。これが正解。 エ: 「1110」はS1→S2→S1→S2→S2とたどり、最終状態がS2となるため受理されない。 💡 有限オートマトンの問題は、初期状態から1文字ずつ遷移表をたどり、最後に受理状態に着地するかだけを機械的に確認すればよい。