有限オートマトン(ゆうげんオートマトン、英:finite automaton)または有限状態機械(ゆうげんじょうたいきかい、英:finite state machine, FSM)とは、有限個の状態と遷移と動作の組み合わせからなる数学的に抽象化された「ふるまいのモデル」である。デジタル回路やプログラムの設計で使われることがあり、ある一連の状態をとったときどのように論理が流れるかを調べることができる。有限個の「状態」のうち1つの状態をとる。ある時点では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. ed.).Englewood Cliffs, N.J.:Prentice-Hall, Inc..ISBN0-13-913368-2
Bobrow,Leonard S.;Michael A. Arbib(1974年).Discrete Mathematics: Applied Algebra for Computer and Information Science(1st ed. ed.).Philadelphia:W. B. Saunders Company, Inc..ISBN0-7216-1768-9
Booth,Taylor L.(1967年).Sequential Machines and Automata Theory(1st ed.).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. ed.).Cambridge, England:Cambridge University Press.ISBN0-521-20402-X
Brookshear,J. Glenn(1989年).Theory of Computation: Formal Languages, Automata, and Complexity.Redwood City, California:Benjamin/Cummings Publish Company, Inc..ISBN0-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. ed.).San Diego:Academic Press, Harcourt, Brace & Company.ISBN0-12-206382-1
Hopcroft,John;Jeffrey Ullman(1979年).Introduction to Automata Theory, Languages and Computation(1st ed. ed.).Reading Mass:Addison-Wesley.ISBN0-201-02988-X
Hopcroft,John E.;Rajeev Motwani, Jeffrey D. Ullman(2001年).Introduction to Automata Theory, Languages, and Computation(2nd ed. ed.).Reading Mass:Addison-Wesley.ISBN0-201-44124-1
Kozen,Dexter C.(1997).Automata and Computability(1st ed. ed.).New York:Springer-Verlag.ISBN0-387-94907-0
Lewis,Harry R.;Christos H. Papadimitriou(1998年).Elements of the Theory of Computation(2nd ed.).Upper Saddle River, New Jersey:Prentice-Hall.ISBN0-13-262478-8
Linz,Peter(2006).Formal Languages and Automata(4th ed.).Sudbury, MA:Jones and Bartlett.ISBN978-0-7637-3798-6
Minsky,Marvin(1967年).Computation: Finite and Infinite Machines(1st ed.).New Jersey:Prentice-Hall
Pippenger,Nicholas(1997年).Theories of Computability(1st ed.).Cambridge, England:Cambridge University Press.0-521-55380-6 (hc)
Rodger,Susan;Thomas Finley(2006年).JFLAP: An Interactive Formal Languages and Automata Package(1st ed.).Sudbury, MA:Jones and Bartlett.ISBN0-7637-3834-4
Sipser,Michael(2006年),Introduction to the Theory of Computation, Second Edition(2nd ed.),Boston Mass:Thomson Course Technology,ISBN0-534-95097-3
Wood,Derick(1987年).Theory of Computation(1st ed.).New York:Harper & Row, Publishers, Inc..ISBN0-06-047208-1
Booth,Taylor L.(1967年).Sequential Machines and Automata Theory(1st ed.).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 ed.).New York:John Wiley and Sons, Inc..ISBN0-471-08840-4
McCluskey,E. J.(1965年).Introduction to the Theory of Switching Circuits(1st ed.).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 ed.).New York:McGraw-Hill Book Company.Library of Congress Card Catalog Number 65-17394
有限マルコフ連鎖プロセス
Booth,Taylor L.(1967年).Sequential Machines and Automata Theory(1st ed.).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 ed.).Englewood Cliffs, N.J.:Prentice-Hall, Inc..Library of Congress Card Catalog Number 59-12841