問題11
図で表される有限オートマトンで受理される文字列はどれか。ここで，
は初期状態を，
は受理状態を表す。
| ア | 01011 |
| イ | 01111 |
| ウ | 10111 |
| エ | 11110 |
解答・解説を見る
解答：ウ
| ア | × | S | → | S | → | A | → | S | → | A | → | B |
| 0 | 1 | 0 | 1 | 1 | ||||||||
| イ | × | S | → | S | → | A | → | B | → | G | → | C |
| 0 | 1 | 1 | 1 | 1 | ||||||||
| ウ | ○ | S | → | A | → | S | → | A | → | B | → | G |
| 1 | 0 | 1 | 1 | 1 | ||||||||
| エ | × | S | → | A | → | B | → | G | → | C | → | C |
| 1 | 1 | 1 | 1 | 0 |
よってウが正解である。