平成26年 春期 応用情報技術者 午前 問4

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

0 1
a a b
b c d
c a b
d c d

 ア  a
 イ  b
 ウ  c
 エ  d


答え ウ


解説
110のデータを各状態から処理した結果を調べて、受理状態を求める。

したがって、c(ウ)の状態を受理状態とすればよい。


キーワード
・有限オートマトン
・状態遷移表

キーワードの解説

戻る 一覧へ 次へ