有限オートマトン
出典: フリー百科事典『ウィキペディア（Wikipedia）』
有限オートマトン（ゆうげん-、finite automaton、FA)または有限状態機械（ゆうげんじょうたいきかい、finite state machine、FSM）とは、有限個の状態と遷移と動作の組み合わせからなる「ふるまいのモデル」である。
状態（state）とは過去に関する情報を格納するものであり、システムが開始してから現在までの入力を反映するものである。 遷移（transition）とは状態変化を示すものであり、遷移を実現するのに必要な条件とともに示される。 動作（action）とは活動の説明であり、与えられた時点で実行しなければならないことを示している。 動作にはいくつかの型がある。
- 開始（Entry）動作
- その状態に入るときに行う動作
- 終了（Exit）動作
- その状態から出るときに行う動作
- 入力（Input）動作
- 現在状態と入力条件に依存して行う動作
- 遷移（Transition）動作
- ある遷移を行うときに実行される動作
有限オートマトンは図1のように状態遷移図で表すことができる。 それと共にある種の状態遷移表が使用される。 最も一般的な形式を下に示す。 現在の状態（B）と条件（Y）の交差するところに次の状態（C）が示される。 完全な動作についての情報は脚注の形で追記される。 完全な動作についての情報を持つ有限オートマトンの定義は、仮想有限状態機械の状態表を使えば可能である。
| 現在状態/ 条件 |
状態 A | 状態 B | 状態 C |
| 条件 X | ... | ... | ... |
| 条件 Y | ... | 状態 C | ... |
| 条件 Z | ... | ... | ... |
ここで示しているような反応性システムの設計だけでなく、有限オートマトンは言語学、情報工学、哲学、生物学、数学、論理学など様々な領域で利用される。 ここでそれらの領域の使用方法を全て述べることはできない。有限オートマトンはオートマトン理論や計算理論で研究される一種のオートマトンである。 情報工学では、アプリケーションの動作のモデリング、ハードウェアの設計、ソフトウェア工学、コンパイラ、計算と言語に関する研究などで幅広く活用されている。
目次 |
[編集] 分類
有限オートマトンは二種類に分類される。アクセプタ/リコグナイザとトランスデューサである。
[編集] アクセプタ/リコグナイザ
このタイプの有限オートマトンは入力を受容（accept）したり、理解（recognize）して、外界に結果を知らせるために状態（state）を使用する。 動作（action）は使用されない。 図2 に示した例は "nice" という単語を受容する有限オートマトンを示している。
[編集] トランスデューサ
トランスデューサ（変換機、transducer）は、与えられた入力と動作を伴う状態（両方または一方）に基づいて出力を生成する。 このタイプの有限オートマトンはアプリケーション（実際の応用例）の制御に使われる。 また、トランスデューサは二種類に分類される。
- ムーア・マシン
- この有限オートマトンは開始動作のみを使用する。すなわち、出力は状態にのみ依存する。ムーア・モデルの利点はふるまいを単純化できることである。図3の例はエレベーターの扉についてのムーア・マシンを示している。この有限オートマトンは「開放命令」と「閉鎖命令」というふたつの命令を理解し、それによって状態が変化する。「開放途中」状態にある開始動作（E:）は扉の開くところを監視し始めることを示し、「閉鎖途中」状態にある開始動作（E:）は扉の閉じるところを監視し始めることを意味する。「開放」と「閉鎖」状態は動作を伴わないが、これらは外界（つまり他のオートマトン）に扉が開いているとか閉まっているといった状況を知らせる意味を持つ。
- ミーリ・マシン
- この有限オートマトンは入力動作のみを使用する。すなわち、出力は入力と状態に依存する。ミーリ・モデルは状態の数を減らす作用がある。図4の例はムーア・マシンの例と同じものをミーリ・マシンで実装したものを示している（実装された有限オートマトンのふるまいは実行モデルに依存する。例えば仮想有限オートマトンでは動作するが、イベント駆動有限オートマトンでは動作しない）。これは二つの入力動作を持つ。「閉鎖命令が来たら扉を閉めるためにモーターを起動する」という入力動作と「開放命令が来たら扉を開けるためにモーターを起動する」という入力動作である。
実際には、これらを混合したモデルがよく使用される。
ムーア・モデルとミーリ・モデルの違いの詳細は、実施例も含めて外部サイトの"Moore or Mealy model?"にある（ただし英語）。
さらなる分類方法として、決定性有限オートマトンと非決定性有限オートマトンがある。 決定性有限オートマトンでは、各状態の考えられる全ての入力について一意に次の状態が決定される。 非決定性有限オートマトンでは、ある状態にある入力があったとき遷移がどうなるかが決定されない（遷移がないかもしれないし、複数の遷移が対応しているかもしれない）。
ひとつしか状態を持たない有限オートマトンは結合有限オートマトンと呼ばれ、入力動作のみを持つ。 これは複数の有限オートマトンが協調動作する場合に便利であり、結合有限オートマトンとして表せる部分を抽出して設計に活用する。
[編集] FSM 論理
有限オートマトン（有限状態機械＝FSM）の次の状態と出力は入力と現在の状態によって決定される。 FSM論理を図5に示す。
[編集] 数学モデル
タイプによって、いくつかの定義が存在する。 アクセプタ有限オートマトンは<Σ, S, s0, δ, F>の5要素から構成される。
- Σ は入力文字セット（有限だが空ではないシンボルの集合）
- S は有限であって空でない状態の集合
- s0 は Sの要素でもある初期状態
- δ は状態遷移関数: δ: S x Σ → S
- F は終了状態の集合であり、 Sの部分集合（空もありうる）
トランスデューサ有限オートマトンは<Σ, Γ, S, s0, δ, ω>の6要素から構成される。
- Σ は入力文字セット（有限だが空ではないシンボルの集合）
- Γ は出力文字セット（有限だが空ではないシンボルの集合）
- S は有限であって空でない状態の集合
- s0 は Sの要素でもある初期状態
- δ は状態遷移関数: δ: S x Σ → S
- ω は出力関数
出力関数が状態と入力文字の関数(ω: S x Σ → Γ )ならば、その定義はミーリ・モデルである。 出力関数が状態のみに依存する(ω: S → Γ )ならば、その定義はムーア・モデルである。
[編集] 最適化
有限オートマトンの最適化とは、同じ機能を実現するのに必要とされる状態の数をいかに減らすかを意味する。 この問題はグラフ彩色の手法を使うことで解決する。
[編集] 実装
[編集] ハードウェアへの適用例
デジタル回路では、プログラマブルロジックデバイス、プログラマブルロジックコントローラ、論理ゲート、フリップフロップ、リレーなどを使って有限オートマトンが構成される。もっと具体的に言えば、状態を格納するレジスタを持ち、状態遷移を決定する論理回路と出力を決定する論理回路を持つハードウェアが有限オートマトンであると言える。
[編集] ソフトウェアへの適用例
有限オートマトンを使ったソフトウェアアプリケーションを作るのに以下のコンセプトが一般に使われる。
- イベント駆動有限オートマトン
- 仮想有限オートマトン
[編集] ツール
[編集] 関連項目
- 正規言語 - 有限オートマトンによって表現できる言語のクラス
- ペトリネット
- シミュレーション
- マービン・ミンスキー
- 状態遷移図
