平成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のデータを各状態から処理した結果を調べて、受理状態を求める。

  • 状態aからの時
    状態aで1を処理すると、状態bに遷移する。
    状態bで1を処理すると、状態dに遷移する。
    状態dで0を処理すると、状態cに遷移する。
  • 状態bからの時
    状態bで1を処理すると、状態dに遷移する。
    状態dで1を処理すると、状態dのままである。
    状態dで0を処理すると、状態cに遷移する。
  • 状態cからの時
    状態cで1を処理すると、状態bに遷移する。
    状態bで1を処理すると、状態dに遷移する。
    状態dで0を処理すると、状態cに遷移する。
  • 状態dからの時
    状態dで1を処理すると、状態dのままである。
    状態dで1を処理すると、状態dのままである。
    状態dで0を処理すると、状態cに遷移する。
したがって、c(ウ)の状態を受理状態とすればよい。


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

キーワードの解説
  • 有限オートマトン
    有限個の状態と有限個の事象からなるものの動作を表現するもの。
    通常は状態遷移図で表されることが多い。
    状態遷移図では状態を○状態の遷移を→で表し、事象は→の添え字で記述する。
  • 状態遷移表
    有限オートマトンを表現するのに表を用いたもので、各状態についての各事象の動作をすべて記述することが可能である。
    制御系のソフトウェア開発では、状態遷移表を書いて設計を行うことが多い。
    状態遷移表を書くためのツールもある。

もっと、「状態遷移表」について調べてみよう。

戻る 一覧へ 次へ