次に示す有限オートマトンが受理する入力例はどれか。
ここで、S1は初期状態を、S3は受理状態を表している。
ア | 1011 |
イ | 1100 |
ウ | 1101 |
エ | 1110 |
答え ウ
【解説】
選択肢の入力を行ったときの動作を確認する。
ア | 1011を入力すると、S1−(1)→S2−(0)→S2−(1)→S1−(1)→S2になり、受理しない。 |
イ | 1100を入力すると、S1−(1)→S2−(1)→S1−(0)→S3−(0)→S2になり、受理しない。 |
ウ | 1101を入力すると、S1−(1)→S2−(1)→S1−(0)→S3−(1)→S3になり、受理する。 |
エ | 1110を入力すると、S1−(1)→S2−(1)→S1−(1)→S2−(0)→S2になり、受理しない。 |
【キーワード】
・有限オートマトン