平成28年度 秋期 応用情報技術者試験 午前 問4
表は，入力記号の集合が{0，1}，状態集合が{a，b，c，d}である有限オートマトンの状態遷移表である。長さ3以上の任意のビット列を左（上位ビット）から順に読み込んで最後が110で終わっているものを受理するには，どの状態を受理状態とすればよいか。
| 0 | 1 | |
|---|---|---|
| a | a | b |
| b | c | d |
| c | a | b |
| d | c | d |
キーボード：1〜4 で解答 → 次の問題 ← 前の問題
正解と解説を見る
解答する前に解説を開いたので、この問題は「見て解いた」として記録します（正解数には入りません）。
正解：ウ
最後の3ビット「110」を読み込んだときに，直前の状態にかかわらず必ず到達する状態を調べます。表から，各状態で 1 → 1 → 0 の順に読み込むと次のようになります。
- a →(1) b →(1) d →(0) c
- b →(1) d →(1) d →(0) c
- c →(1) b →(1) d →(0) c
- d →(1) d →(1) d →(0) c
どの状態から始めても，110を読み込んだ後は必ず状態cになります。したがって，cを受理状態とすればよいことになります。
-
ア: a
誤り。aは状態a，cで0を読み込んだときの遷移先です。110の最後の0は状態dで読み込まれるため，遷移先はcになり，aにはなりません。 -
イ: b
誤り。bは状態a，cで1を読み込んだときの遷移先です。最後が0で終わる110では到達しません。 -
ウ: c
正しい。上の追跡のとおり，どの状態からでも110を読み込むとcに到達します。 -
エ: d
誤り。dは11を読み込んだ直後の状態です。その後0を読み込むとcに遷移します。
答え
ウ: c
出典：平成28年度 秋期 応用情報技術者試験 午前 問4
