有限オートマトン（)または有限状態機械（）とは、有限個の状態と遷移と動作の組み合わせからなる数学的に抽象化された「ふるまいのモデル」である。デジタル回路やプログラムの設計で使われることがあり、ある一連の状態をとったときどのように論理が流れるかを調べることができる。有限個の「状態」のうち1つの状態をとる。ある時点では1つの状態しかとらず、それをその時点の「現在状態」と呼ぶ。何らかのイベントや条件によってある状態から別の状態へと移行し、それを「遷移」と呼ぶ。それぞれの現在状態から遷移しうる状態と、遷移のきっかけとなる条件を列挙することで定義される。有限オートマトンは様々な問題に応用でき、半導体設計の自動化、通信プロトコル設計、構文解析などの工学面での応用がある。生物学や人工知能研究では状態機械（群）を使って神経系をモデル化し、言語学では自然言語の文法をモデル化したりする。状態は、システムの振る舞いのノードであり、システム内で遷移を実行するトリガーを待っている。一般に状態は、同じトリガーに対してシステムの反応が常に同じではない場合に導入される。例えば、カーラジオのシステムでは、特定のラジオ局の放送を聴いている状態で「次へ」というトリガーは次のラジオ局（の放送受信）への移行を意味する。しかし、CDプレーヤーのシステムでは、「次へ」は次のトラックへの移行を意味する。これらは、同じトリガーであっても現在状態によって異なる動作を引き起こす。一部の有限オートマトンの表現では、次のように動作と状態を対応付けることもある。遷移は、条件が満たされたときまたはイベントを受信したときに実行される動作の集合である。有限オートマトンは図のように状態遷移図で表すことができる。それと共にある種の状態遷移表が使用される。最も一般的な形式を下に示す。現在の状態（例えばB）と入力（例えばY）の交差するところに次の状態（例えばC）が示される。完全な動作についての情報は脚注の形で追記される。完全な動作についての情報を持つ有限オートマトンの定義は、の状態表を使えば可能である。統一モデリング言語(UML)には状態機械（ステートマシン）を記述するための豊富な意味論と記法がある。UMLの状態遷移図は従来の有限オートマトンの主な利点を踏襲しつつ、その欠点を克服している。大きな拡張としては、状態の階層化や直交状態の導入があり、動作の記法も拡張されている。ミーリ・マシンもムーア・マシンも記述できる。ミーリ・マシンのように状態だけでなく、イベント（入力）をきっかけとして遷移するようにも書けるし、ムーア・マシンのように遷移ではなく状態と開始動作や終了動作を対応付けることもできる。仕様及び記述言語(SDL) はITUの標準規格であり、遷移の際の以下のような動作を表す記号を定義している。SDLには、Abstract Data Types と呼ばれる基本データ型、動作言語、有限状態機械を実行可能にするための実行意味論を埋め込む。有限オートマトンには他にも様々な表現方法があり、例えば図3もその一種である。ここで示しているような反応性システムの設計だけでなく、有限オートマトンは電気工学、言語学、計算機科学、哲学、生物学、数学、論理学など様々な領域で利用される。有限オートマトンはオートマトン理論や計算理論で研究される一種のオートマトンである。情報工学や計算機科学では、アプリケーションの動作のモデリング、デジタルシステムのハードウェア設計、ソフトウェア工学、コンパイラ設計、通信プロトコルの設計、計算と言語に関する研究などで幅広く活用されている。有限オートマトンは二種類に分類される。アクセプタ/リコグナイザとトランスデューサである。このタイプの有限オートマトンは入力を受容（accept）したり、理解（recognize）して、外界に結果を知らせるために状態（state）を使用する。つまり、最終的に受容状態になったかどうかで「はい」または「いいえ」のいずれかを出力として返す。FSMの全状態は受容状態かそうでないかのいずれかである。全入力を処理したとき状態が受容状態なら、その入力は受容されたことになり、さもなくば拒絶/却下されたことになる。基本的に入力は記号（または文字）であり、動作（action）は使用されない。図4 に示した例は "nice" という単語を受容する有限オートマトンを示している。この場合、6番だけが受容状態である。この機械は言語を定義するものとして説明することもできる。その言語とは、その機械が受容する全ての単語から構成され、それ以外の単語を全く含まないもので、そのような言語をその機械が「受容/受理」すると称する。定義から、FSM が受理する言語は正規言語であり、逆にある言語を受理する FSM が存在する場合、その言語を正規言語と称する。初期状態は、一般にどこからも矢印で指されていない状態である。受容状態は、その機械が手続きを成功裡に完了させた状態である。通常、二重丸で表現される。図5の決定性有限オートマトン (DFA) は2進数の入力が偶数個の 0 を含むときに受容することを示している。"S" は初期状態でもあり、受容状態でもある。この機械は入力数列に"0"が偶数個含まれるときのみ正しく終了したと判定され、0個も偶数なので"0"が全く含まれない数字列も受容される。このDFAが受容する文字列の例としては、ε（空文字列）、1、11、00、010、1010、10110、などなどがある。トランスデューサ（変換機、transducer）は、与えられた入力と動作を伴う状態（両方または一方）に基づいて出力を生成する。このタイプの有限オートマトンは計算言語学の分野や制御などに使われる。また、トランスデューサは二種類に分類される。実際には、これらを混合したモデルがよく使用される。ムーア・モデルとミーリ・モデルの違いの詳細は、実施例も含めて外部サイトの"Moore or Mealy model?"にある（ただし英語）。さらなる分類方法として、決定性有限オートマトン (DFA) と非決定性有限オートマトン (NFA, GNFA) がある。決定性有限オートマトンでは、各状態の考えられる全ての入力について一意に次の状態が決定される。非決定性有限オートマトンでは、ある状態にある入力があったとき遷移がどうなるかが決定されない（遷移がないかもしれないし、複数の遷移が対応しているかもしれない）。このような区別は実行時間などの観点では重要だが、ふるまいに関する観点ではそれほど重要ではない。それぞれのオートマトンで表現可能なふるまいは同じであり、任意のNFAを等価な（しかしより大きな）DFAに変換するアルゴリズムが存在する（冪集合構築）。ひとつしか状態を持たない有限オートマトンは結合有限オートマトンと呼ばれ、入力動作のみを持つ。これは複数の有限オートマトンが協調動作する場合に便利であり、結合有限オートマトンとして表せる部分を抽出して設計に活用する。有限オートマトンを表現する他の意味論も存在する。たとえば、組み込みコントローラ用論理回路をモデリング・設計するツールが存在する。階層的な状態機械、フローグラフ、真理値表を1つの言語に統合し、異なる形式手法と意味論の集合を生ずる。Harelの独自のステートマシン図などは、階層型の入れ子になった状態、直交領域、状態動作、遷移動作などをサポートしている。有限オートマトン（有限状態機械＝FSM）の次の状態と出力は入力と現在の状態によって決定される。FSM論理を図8に示す。タイプによって、いくつかの定義が存在する。アクセプタ有限オートマトンは<"Σ

出典:wikipedia