有限オートマトン
デジタル回路では、プログラマブルロジックデバイス、プログラマブルロジックコントローラ、論理ゲート、フリップフロップ、リレーなどを使って有限オートマトンが構成される。もっと具体的に言えば、状態を格納するレジスタを持ち、状態遷移を決定する論理回路と出力を決定する論理回路を持つハードウェアが有限オートマトンであると言える。初期のハードウェア実装として Richards controller がある。
フリップフロップと出力の間には伝播遅延が存在するため、ミーリ・マシンやムーア・マシンからは非同期出力の論理回路が生成される。このため動作周波数が遅くなってしまう。ミーリ・マシンやムーア・マシンはフリップフロップから直接出力する形に変換でき、そうすることで動作周波数を高めることができる。このように変換した有限状態機械を Medvedev FSM と呼ぶことがある。その最も単純な例としてカウンタ回路がある。
有限オートマトンの最適化とは、同じ機能を実現するのに必要とされる状態の数をいかに減らすかを意味する。既知の最速のアルゴリズムとして Hopcroft minimization algorithm がある。他にも Implication table や Moore reduction procedure といった手法が使われる。また、非環状FSAは線型時間で最小化できる。
有限オートマトンを使ったソフトウェアアプリケーションを作るのに以下のコンセプトが一般に使われる。
イベント駆動有限オートマトン(英語版)
仮想有限オートマトン(英語版)
Automata-based programming