Web教材一覧ハードウェアとソフトウェア

オートマトンと状態遷移図

キーワード

オートマトン、チューリングマシン、状態遷移図、状態遷移表


オートマトンの概念およびそれを記述する状態遷移図は、論理回路の設計やソフトウェアの設計に重要なものになっています。
 例えば右図は、OSのタスク管理において、タスクの状態の遷移を図示したものです。
 新しくタスクが生成されると、まず「実行可能状態」になります(①)。その状態にある複数のタスクからディスパッチャにより選択されたタスクは「実行状態」に遷移(②)して実行され(CPUが割り当てられ)、実行が終了すればタスクは消滅します(⑥)。実行している間に、なんらかの割込みが発生して、他のタスクにCPUが割り当てられると、このタスクは「待機状態」に遷移します(④)。以下省略(詳細は「タスク管理」(hs-task-kanri)参照)

状態遷移の動きを例題で解説します。
○問題
 下の状態遷移図あるいは状態遷移表と入力が与えられたとき、遷移の過程を示せ。
 

       遷移先
    A B C D E
  A 0 1
遷 B 0     1
移 C 0       1
元 D 0   1
  E 0,1

入力  ア:10111   イ:11110

○解答
アの場合:①1→②0→③1→④1→⑤1のように入力番号をつけます。

  1. 初期状態Aでは、入力が0なら遷移せずにAの状態が継続し、1ならばBへ遷移することを示しています、①の入力が1なので、Bへ遷移します。
  2. ②では、Bにおいて0が入力されたので、Aへ戻ります。
  3. ③では、Aにおいて1が入力されたので、Bへ遷移します。
  4. ④では、Bにおいて1が入力されたので、Dへ遷移します。
  5. ⑤では、Dにおいて1が入力されたので、Cへ遷移します。この結果、受理状態に達しました。

イの場合:次の遷移になるので、受理状態にならず拒否されます。
  A(1)→B(1)→D(1)→C(1)→E(0)→E