3-9　オートマトン

令和7年1月修了試験　 問3

表は,入力記号の集合が｛0, 1｝,状態集合が｛a, b, c, d｝である有限オートマトンの状態遷移表である。長さ3以上の任意のビット列を左(上位ビツト)から順に読み込んで最後が110で終わっているものを受理するには,どの状態を受理状態とすればよいか。

解答　ウ

【頭の準備体操】
オートマトンは，現在の状態と入力によって，出力が決定される機械をモデル化したもの。
有限オートマトンは，オートマトンのうち，初期状態からいくつかの状態を遷移し，最終的に受理状態(終了状態)になるもの。

【イメージで解く】
状態遷移表から下図の状態遷移図になる。

aの状態から，
a →(1)→ b →(1)→ d→ (0)→ c

bの状態から，
b →(1)→ d →(1)→ d→ (0)→ c

cの状態から，
c →(1)→ b →(1)→ d→ (0)→ c

dの状態から，
d →(1)→ d →(1)→ d→ (0)→ c

よって，cの状態を受理すればよい。