問題3
次に示す有限オートマトンが受理する入力列はどれか。ここで、S1は初期状態を、S3は受理状態を表している。
| ア | 1011 |
| イ | 1100 |
| ウ | 1101 |
| エ | 1110 |
解答・解説を見る
解答：ウ
| ア | × | 1011： | S1 -(1)→ S2 -(0)→ S2 -(1)→ S1 -(1)→ S2と遷移する。S2で終わるので誤りである。 |
| イ | × | 1100： | S1 -(1)→ S2 -(1)→ S1 -(0)→ S3 -(0)→ S2と遷移する。S2で終わるので誤りである。 |
| ウ | ○ | 1101： | S1 -(1)→ S2 -(1)→ S1 -(0)→ S3 -(1)→ S3と遷移する。S3(受理状態)で終わるので正解である。 |
| エ | × | 1110： | S1 -(1)→ S2 -(1)→ S1 -(1)→ S2 -(0)→ S2と遷移する。S2で終わるので誤りである。 |