応用情報技術者平成28年秋期午前4

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

１、表の有限オートマトンを図にする　※これが大事です。

２、
・ビット列「110」が入力されるときに、a～dのどの状態であるかはわかりませんが、最後の0が入力されて遷移する先はaかcのどちらかしかないですね。

xxc
or
xxa　です。

・cが最後とすると
a->(1)->b->(1)->d->(1)->c
。。。
正しいのようですね。

・aが最後とすると
cのみが来るので、且つ0ので、110にはできないですね。