有限オートマトン

有限オートマトンの最新ニュースをまとめて検索！

図1 有限オートマトン

有限オートマトン（ゆうげん-、finite automaton、FA)または有限状態機械（ゆうげんじょうたいきかい、finite state machine、FSM）とは、有限個の状態と遷移と動作の組み合わせからなる「ふるまいのモデル」である。

[編集] 概念と用語

状態（state）とは過去に関する情報を格納するものであり、システムが開始してから現在までの入力を反映するものである。 遷移（transition）とは状態変化を示すものであり、遷移を実現するのに必要な条件とともに示される。 動作（action）とは活動の説明であり、与えられた時点で実行しなければならないことを示している。 動作にはいくつかの型がある。

開始（Entry）動作

その状態に入るときに行う動作

終了（Exit）動作

その状態から出るときに行う動作

入力（Input）動作

現在状態と入力条件に依存して行う動作

遷移（Transition）動作

ある遷移を行うときに実行される動作

有限オートマトンは図1のように状態遷移図で表すことができる。 それと共にある種の状態遷移表が使用される。 最も一般的な形式を下に示す。 現在の状態（B）と条件（Y）の交差するところに次の状態（C）が示される。 完全な動作についての情報は脚注の形で追記される。 完全な動作についての情報を持つ有限オートマトンの定義は、仮想有限状態機械の状態表を使えば可能である。

ここで示しているような反応性システムの設計だけでなく、有限オートマトンは言語学、情報工学、哲学、生物学、数学、論理学など様々な領域で利用される。 ここでそれらの領域の使用方法を全て述べることはできない。有限オートマトンはオートマトン理論や計算理論で研究される一種のオートマトンである。 情報工学では、アプリケーションの動作のモデリング、ハードウェアの設計、ソフトウェア工学、コンパイラ、計算と言語に関する研究などで幅広く活用されている。

[編集] 分類

有限オートマトンは二種類に分類される。アクセプタ/リコグナイザとトランスデューサである。

[編集] アクセプタ/リコグナイザ

図2 アクセプタFSM: "nice"を語句解析する

このタイプの有限オートマトンは入力を受容（accept）したり、理解（recognize）して、外界に結果を知らせるために状態（state）を使用する。 動作（action）は使用されない。 図2 に示した例は "nice" という単語を受容する有限オートマトンを示している。

この機械は言語を定義するものとして説明することもできる。その言語とは、その機械が受容する全ての単語から構成され、それ以外の単語を全く含まないもので、そのような言語をその機械が「受容/受理」すると称する。定義から、FSM が受理する言語は正規言語であり、逆にある言語を受理する FSM が存在する場合、その言語を正規言語と称する。

[編集] 初期状態/開始状態

受容状態の例

初期状態は、一般にどこからも矢印で指されていない状態である（Sipser (2006) p.34）

[編集] 受容状態/受理状態

受容状態は、その機械が手続きを成功裡に完了させた状態である。通常、二重丸で表現される。

右図の有限オートマトンは二進記数法の入力が偶数個の 0 を含むときに受容することを示している。S₁ は初期状態でもある。

[編集] トランスデューサ

トランスデューサ（変換機、transducer）は、与えられた入力と動作を伴う状態（両方または一方）に基づいて出力を生成する。 このタイプの有限オートマトンはアプリケーション（実際の応用例）の制御に使われる。 また、トランスデューサは二種類に分類される。

図3 Fig. 3 トランスデューサFSM: ムーア・モデルの例

ムーア・マシン

この有限オートマトンは開始動作のみを使用する。すなわち、出力は状態にのみ依存する。ムーア・モデルの利点はふるまいを単純化できることである。図3の例はエレベーターの扉についてのムーア・マシンを示している。この有限オートマトンは「開放命令」と「閉鎖命令」というふたつの命令を理解し、それによって状態が変化する。「開放途中」状態にある開始動作（E:）は扉の開くところを監視し始めることを示し、「閉鎖途中」状態にある開始動作（E:）は扉の閉じるところを監視し始めることを意味する。「開放」と「閉鎖」状態は動作を伴わないが、これらは外界（つまり他のオートマトン）に扉が開いているとか閉まっているといった状況を知らせる意味を持つ。

図4 トランスデューサFSM: ミーリ・モデルの例

ミーリ・マシン

この有限オートマトンは入力動作のみを使用する。すなわち、出力は入力と状態に依存する。ミーリ・モデルは状態の数を減らす作用がある。図4の例はムーア・マシンの例と同じものをミーリ・マシンで実装したものを示している（実装された有限オートマトンのふるまいは実行モデルに依存する。例えば仮想有限オートマトンでは動作するが、イベント駆動有限オートマトンでは動作しない）。これは二つの入力動作を持つ。「閉鎖命令が来たら扉を閉めるためにモーターを起動する」という入力動作と「開放命令が来たら扉を開けるためにモーターを起動する」という入力動作である。

実際には、これらを混合したモデルがよく使用される。

ムーア・モデルとミーリ・モデルの違いの詳細は、実施例も含めて外部サイトの"Moore or Mealy model?"にある（ただし英語）。

さらなる分類方法として、決定性有限オートマトンと非決定性有限オートマトンがある。 決定性有限オートマトンでは、各状態の考えられる全ての入力について一意に次の状態が決定される。 非決定性有限オートマトンでは、ある状態にある入力があったとき遷移がどうなるかが決定されない（遷移がないかもしれないし、複数の遷移が対応しているかもしれない）。

ひとつしか状態を持たない有限オートマトンは結合有限オートマトンと呼ばれ、入力動作のみを持つ。 これは複数の有限オートマトンが協調動作する場合に便利であり、結合有限オートマトンとして表せる部分を抽出して設計に活用する。

[編集] FSM 論理

図5 FSM 論理

有限オートマトン（有限状態機械＝FSM）の次の状態と出力は入力と現在の状態によって決定される。 FSM論理を図5に示す。

[編集] 数学モデル

タイプによって、いくつかの定義が存在する。 アクセプタ有限オートマトンは<Σ, S, s₀, δ, F>の5要素から構成される。

• Σ は入力文字セット（有限だが空ではないシンボルの集合）
• S は有限であって空でない状態の集合
• s₀ は Sの要素でもある初期状態
• δ は状態遷移関数: δ: S x Σ → S
• F は終了状態の集合であり、 Sの部分集合（空もありうる）

トランスデューサ有限オートマトンは<Σ, Γ, S, s₀, δ, ω>の6要素から構成される。

• Σ は入力文字セット（有限だが空ではないシンボルの集合）
• Γ は出力文字セット（有限だが空ではないシンボルの集合）
• S は有限であって空でない状態の集合
• s₀ は Sの要素でもある初期状態
• δ は状態遷移関数: δ: S x Σ → S
• ω は出力関数

出力関数が状態と入力文字の関数(ω: S x Σ → Γ )ならば、その定義はミーリ・モデルである。 出力関数が状態のみに依存する(ω: S → Γ )ならば、その定義はムーア・モデルである。

[編集] 最適化

有限オートマトンの最適化とは、同じ機能を実現するのに必要とされる状態の数をいかに減らすかを意味する。 この問題はグラフ彩色の手法を使うことで解決する。

[編集] 実装

[編集] ハードウェアへの適用例

図6 4ビットTTLカウンタの回路図、一種のオートマトン

デジタル回路では、プログラマブルロジックデバイス、プログラマブルロジックコントローラ、論理ゲート、フリップフロップ、リレーなどを使って有限オートマトンが構成される。もっと具体的に言えば、状態を格納するレジスタを持ち、状態遷移を決定する論理回路と出力を決定する論理回路を持つハードウェアが有限オートマトンであると言える。

[編集] ソフトウェアへの適用例

有限オートマトンを使ったソフトウェアアプリケーションを作るのに以下のコンセプトが一般に使われる。

• イベント駆動有限オートマトン
• 仮想有限オートマトン

[編集] ツール

[編集] 関連項目

• 正規言語 - 有限オートマトンによって表現できる言語のクラス
• オートマトン
  • プッシュダウン・オートマトン
  • 線形拘束オートマトン
  • チューリングマシン
• ペトリネット
• シミュレーション
• マービン・ミンスキー
• 状態遷移図
• 隠れマルコフモデル

[編集] 参考文献

[編集] 一般

• Wagner, F., "Modeling Software with Finite State Machines: A Practical Approach", Auerbach Publications, 2006, ISBN 0-8493-8086-3.
• Samek, M., "Practical Statecharts in C/C++", CMP Books, 2002, ISBN 1-57820-110-1.
• Cassandras, C., Lafortune, S., "Introduction to Discrete Event Systems". Kluwer, 1999, ISBN 0-7923-8609-4.
• Timothy Kam, Synthesis of Finite State Machines: Functional Optimization. Kluwer Academic Publishers, Boston 1997, ISBN 0-7923-9842-4
• Tiziano Villa, Synthesis of Finite State Machines: Logic Optimization. Kluwer Academic Publishers, Boston 1997, ISBN 0-7923-9892-0
• Carroll, J., Long, D. , Theory of Finite Automata with an Introduction to Formal Languages. Prentice Hall, Englewood Cliffs, 1989.
• Kohavi, Z., Switching and Finite Automata Theory. McGraw-Hill, 1978.
• Gill, A., Introduction to the Theory of Finite-state Machines. McGraw-Hill, 1962.
• Ginsburg, S., An Introduction to Mathematical Machine Theory. Addison-Wesley, 1962.

[編集] 理論計算機科学

• Arbib, Michael A. (1969年). Theories of Abstract Automata, 1st ed., Englewood Cliffs, N.J.: Prentice-Hall, Inc.. 
• Bobrow, Leonard S.; Michael A. Arbib (1974年). Discrete Mathematics: Applied Algebra for Computer and Information Science, 1st ed., Philadelphia: W. B. Saunders Company, Inc.. 
• Booth, Taylor L. (1967年). Sequential Machines and Automata Theory, 1st, New York: John Wiley and Sons, Inc.. Library of Congress Card Catalog Number 67-25924. 
• Boolos, George; Richard Jeffrey (1989年, 1999年). Computability and Logic, 3rd ed., Cambridge, England: Cambridge University Press. ISBN 0-521-20402-X. 
• Brookshear, J. Glenn (1989年). Theory of Computation: Formal Languages, Automata, and Complexity. Redwood City, California: Benjamin/Cummings Publish Company, Inc.. ISBN 0-8053-0143-7. 
• Davis, Martin; Ron Sigal, Elaine J. Weyuker (1994年). Second Edition: Computability, Complexity, and Languages and Logic: Fundamentals of Theoretical Computer Science, 2nd ed., San Diego: Academic Press, Harcourt, Brace & Company. 
• Hopcroft, John; Jeffrey Ullman (1979年). Introduction to Automata Theory, Languages and Computation, 1st ed., Reading Mass: Addison-Wesley. ISBN 0-201-02988-X. 
• Hopcroft, John E.; Rajeev Motwani, Jeffrey D. Ullman (2001年). Introduction to Automata Theory, Languages, and Computation, 2nd ed., Reading Mass: Addison-Wesley. 
• Hopkin, David; Barbara Moss (1976年). Automata. New York: Elsevier North-Holland. ISBN 0-444-00249-9. 
• Kozen, Dexter C. (1997). Automata and Computability, 1st ed., New York: Springer-Verlag. ISBN 0-387-94907-0. 
• Lewis, Harry R.; Christos H. Papadimitriou (1998年). Elements of the Theory of Computation, 2nd, Upper Saddle River, New Jersey: Prentice-Hall. ISBN 0-13-262478-8. 
• Linz, Peter (2006). Formal Languages and Automata, 4th, Sudbury, MA: Jones and Bartlett. ISBN-13: 978-0-7637-3798-6. 
• Minsky, Marvin (1967年). Computation: Finite and Infinite Machines, 1st, New Jersey: Prentice-Hall. 
• Christos Papadimitriou (1993年). Computational Complexity, 1st edition, Addison Wesley. ISBN 0-201-53082-1. 
• Pippenger, Nicholas (1997年). Theories of Computability, 1st, Cambridge, England: Cambridge University Press. 0-521-55380-6 (hc). 
• Rodger, Susan; Thomas Finley (2006年). JFLAP: An Interactive Formal Languages and Automata Package, 1st, Sudbury, MA: Jones and Bartlett. ISBN-10: 0763738344. 
• Sipser, Michael (2006年). Introduction to the Theory of Computation, Second Edition, 2nd, Boston Mass: Thomson Course Technology. ISBN-10: 0-534-95097-3. 
• Wood, Derick (1987年). Theory of Computation, 1st, New York: Harper & Row, Publishers, Inc.. ISBN-10: 0-06-047208-1. 
• Yuri Gurevich (2000), Sequential Abstract State Machines Capture Sequential Algorithms, ACM Transactions on Computational Logic, vl. 1, no. 1 (July 2000), pages 77-111. http://research.microsoft.com/~gurevich/Opera/141.pdf

[編集] 機械学習

• Mitchell, Tom M. (1997年). Machine Learning, 1st, New York: WCB/McGraw-Hill Corporation. ISBN 0-07-042807-7. 

[編集] 回路合成などハードウェアへの応用

• Booth, Taylor L. (1967年). Sequential Machines and Automata Theory, 1st, New York: John Wiley and Sons, Inc.. Library of Congress Card Catalog Number 67-25924. 
• Booth, Taylor L. (1971年). Digital Networks and Computer Systems, 1st, New York: John Wiley and Sons, Inc.. ISBN 0-471-08840-4. 
• McCluskey, E. J. (1965年). Introduction to the Theory of Switching Circuits, 1st, New York: McGraw-Hill Book Company,Inc.. Library of Congress Card Catalog Number 65-17394. 
• Hill, Fredrick J.; Gerald R. Peterson (1965年). Introduction to the Theory of Switching Circuits, 1st, New York: McGraw-Hill Book Company. Library of Congress Card Catalog Number 65-17394. 

[編集] 有限マルコフ連鎖プロセス

• Booth, Taylor L. (1967年). Sequential Machines and Automata Theory, 1st, New York: John Wiley and Sons, Inc.. Library of Congress Card Catalog Number 67-25924. 
• Kemeny, John G.; Hazleton Mirkil, J. Laurie Snell, Gerald L. Thompson (1959年). Finite Mathematical Structures, 1st, Englewood Cliffs, N.J.: Prentice-Hall, Inc.. Library of Congress Card Catalog Number 59-12841. 

[編集] 外部リンク

• Description from the Free On-Line Dictionary of Computing
• NIST Dictionary of Algorithms and Data Structures entry
• Hierarchical State Machines
• Round-trip Engineering State Machines