有限状態機械

オートマトンの種類

有限状態機械（FSM ）または有限状態オートマトン（FSA、複数形：オートマトン）、有限オートマトン、または単に状態機械は、計算の数学的モデルです。これは、任意の時点で有限の数の状態のうちの1つだけをとることができる抽象機械です。FSMは、いくつかの入力に応答して、ある状態から別の状態へと変化することができます。ある状態から別の状態への変化は、遷移と呼ばれます。 ^[1] FSMは、状態のリスト、初期状態、および各遷移をトリガーする入力によって定義されます。有限状態機械には、決定性有限状態機械と非決定性有限状態機械の2種類があります。^[2]非決定性有限状態機械に対しては、同等の決定性有限状態機械を構築できます。

状態マシンの動作は、現代社会の多くのデバイスで観察できます。これらのデバイスは、提示される一連のイベントに応じて、事前に決定された一連のアクションを実行します。簡単な例としては、適切な組み合わせのコインを入れると商品が出てくる自動販売機、乗客が指定した階数によって停止順序が決まるエレベーター、車が待機しているときに順序が変わる信号機、適切な順序で一連の数字を入力する必要があるダイヤル 錠などがあります。

有限状態機械は、チューリングマシンなどの他の計算モデルに比べて計算能力が低い。^[3]計算能力の違いは、チューリングマシンでは実行できても有限状態機械では実行できない計算タスクがあることを意味する。これは、有限状態機械のメモリが状態数によって制限されるためである。有限状態機械は、ヘッドが「読み取り」操作のみを実行でき、常に左から右に移動する必要があるという制限があるチューリングマシンと同じ計算能力を持つ。有限状態機械は、より一般的なオートマトン理論の分野で研究されている。

ステートマシンでモデル化できる単純なメカニズムの例としては、回転式改札口があります。^{[4] [5]}地下鉄や遊園地の乗り物へのアクセスを制御するために使用される回転式改札口は、腰の高さに 3 つの回転アームが付いたゲートで、1 つは入口を横切っています。最初、アームはロックされており、入口をブロックして、顧客が通過できないようにしています。回転式改札口のスロットにコインまたはトークンを入れると、アームのロックが解除され、1 人の顧客が押し通れるようになります。顧客が通過すると、別のコインが挿入されるまでアームは再びロックされます。

回転式改札機を状態機械として考えると、LockedとUnlocked の2 つの状態が考えられます。^[4]状態に影響を与える入力は 2 つあります。スロットにコインを入れる ( coin ) ことと、アームを押す ( push ) ことです。ロックされた状態では、アームを押しても効果はありません。push入力を何度与えても、ロックされた状態のままです。コインを入れる、つまり機械にコイン入力を与えると、状態はLockedからUnlockedに変わります。ロック解除された状態では、追加のコインを入れても効果はありません。つまり、追加のコイン入力を与えても状態は変わりません。アームを押す顧客はpush入力を与え、状態をLockedにリセットします。

ターンスタイル ステート マシンは、状態遷移表で表すことができます。状態遷移表は、各可能な状態、状態間の遷移 (マシンに与えられた入力に基づく)、および各入力から生じる出力を示します。

ターンスタイル ステート マシンは、状態図(上記)と呼ばれる有向グラフで表すこともできます。各状態はノード(円) で表されます。エッジ (矢印) は、ある状態から別の状態への遷移を示します。各矢印には、その遷移をトリガーする入力のラベルが付けられています。状態の変化を引き起こさない入力 ( Unlocked状態でのコイン入力など) は、元の状態に戻る円形の矢印で表されます。黒い点から Lockedノードに向かう矢印は、それが初期状態であることを示します。

状態とは、遷移の実行を待機しているシステムのステータスの説明です。遷移とは、条件が満たされたとき、またはイベントが受信されたときに実行される一連のアクションです。たとえば、オーディオ システムを使用してラジオを聴く場合 (システムは「ラジオ」状態)、「次の」刺激を受信すると、次のステーションに移動します。システムが「CD」状態にある場合、「次の」刺激を受信すると、次のトラックに移動します。同じ刺激でも、現在の状態に応じて異なるアクションがトリガーされます。

一部の有限状態マシン表現では、アクションを状態に関連付けることもできます。

• エントリアクション：状態に入るときに実行され、
• 終了アクション:状態を終了するときに実行されます。

状態遷移表にはいくつかの種類があります。最も一般的な表現を以下に示します。現在の状態 (例: B) と入力 (例: Y) の組み合わせによって、次の状態 (例: C) が示されます。完全なアクションの情報は表に直接記述されておらず、脚注を使用してのみ追加できます。^{[詳細な説明が必要]完全なアクションの情報を含む FSM 定義は、}状態表を使用して可能です(仮想有限状態マシンも参照)。

統一モデリング言語には、状態マシンを記述するための表記法があります。UML状態マシンは、従来の有限状態マシンの主な利点を維持しながら、その制限^{[引用が必要]を克服しています。UML 状態マシンは、}階層的にネストされた状態と直交領域という新しい概念を導入し、アクションの概念を拡張しています。UML 状態マシンは、 Mealy マシンとMoore マシンの両方の特性を備えています。Mealyマシンのようにシステムの状態とトリガーイベントの両方に依存するアクションと、Moore マシンのように遷移ではなく状態に関連付けられたエントリ アクションと終了アクションをサポートします。 ^{[引用が必要]}

仕様および記述言語は、遷移時のアクションを記述するためのグラフィカル シンボルを含む ITUの標準です。

• イベントを送信する
• イベントを受け取る
• タイマーを開始する
• タイマーをキャンセルする
• 別の同時ステートマシンを起動する
• 決断

SDL は、有限状態マシンを実行可能にするために、「抽象データ型」と呼ばれる基本データ型、アクション言語、および実行セマンティクスを埋め込みます。^{[引用が必要]}

図 3 のような FSM を表すバリエーションは多数あります。

ここで紹介したリアクティブ システムのモデリングでの使用に加えて、有限状態マシンは、電気工学、言語学、コンピュータ サイエンス、哲学、生物学、数学、ビデオ ゲーム プログラミング、論理学など、さまざまな分野で重要です。有限状態マシンは、オートマトン理論と計算理論で研究されるオートマトンの一種です。コンピュータ サイエンスでは、有限状態マシンは、アプリケーションの動作のモデリング (制御理論)、ハードウェア デジタル システムの設計、ソフトウェア エンジニアリング、コンパイラ、ネットワーク プロトコル、計算言語学で広く使用されています。

有限状態機械は、アクセプタ、分類器、トランスデューサ、シーケンサに分類できます。^[6]

アクセプタ(検出器または認識装置とも呼ばれる) は、受信した入力が受け入れられるかどうかを示すバイナリ出力を生成します。アクセプタの各状態は、受け入れまたは非受け入れのいずれかです。すべての入力が受信されると、現在の状態が受け入れ状態であれば、入力は受け入れられ、そうでない場合は拒否されます。原則として、入力は一連のシンボル(文字) であり、アクションは使用されません。開始状態は受け入れ状態になることもあり、その場合、アクセプタは空の文字列を受け入れます。図 4 の例は、文字列 "nice" を受け入れるアクセプタを示しています。このアクセプタでは、受け入れ状態は状態 7 のみです。

形式言語と呼ばれる（おそらく無限の）記号列の集合は、その集合を正確に受け入れる何らかの受容者が存在する場合、正規言語である。 ^[7]たとえば、偶数個のゼロを持つバイナリ文字列の集合は正規言語である（図5を参照）が、長さが素数であるすべての文字列の集合は正規言語ではない。^[8]

アクセプターは、アクセプターが受け入れたすべての文字列を含み、拒否された文字列を含まない言語を定義するとも言えます。つまり、その言語はアクセプターによって受け入れられます。定義により、アクセプターによって受け入れられる言語は通常の言語です。

与えられた受容者が受け入れる言語を決定する問題は代数的経路問題の一例であり、それ自体は（任意の）半環の要素によって重み付けされた辺を持つグラフへの最短経路問題の一般化である。^{[9] [10] [専門用語]}

受け入れ状態の例は、図 5 に示されています。これは、バイナリ入力文字列に偶数個の 0 が含まれている かどうかを検出する決定性有限オートマトン(DFA) です。

S ₁ (開始状態でもある) は、偶数個の 0 が入力された状態を示します。したがって、S _{1 は}受け入れ状態です。バイナリ文字列に偶数個の 0 (0 を含まないバイナリ文字列も含む) が含まれている場合、このアクセプタは受け入れ状態で終了します。このアクセプタによって受け入れられる文字列の例としては、ε (空の文字列)、1、11、11...、00、010、1010、10110 などがあります。

分類器は、 nが2より大きいn値の出力を生成するアクセプタの一般化である。 ^[11]

トランスデューサーは、アクションを使用して、与えられた入力や状態に基づいて出力を生成します。制御アプリケーションや計算言語学の分野で使用されます。

制御アプリケーションでは、次の 2 つのタイプが区別されます。

ムーアマシン

FSM はエントリ アクションのみを使用します。つまり、出力は状態のみに依存します。ムーア モデルの利点は、動作が単純化されることです。エレベータのドアを考えてみましょう。ステート マシンは、状態の変更をトリガーする 2 つのコマンド「command_open」と「command_close」を認識します。ステート「Opening」のエントリ アクション (E:) は、ドアを開くモーターを起動し、ステート「Closing」のエントリ アクションは、ドアを閉じる反対方向のモーターを起動します。ステート「Opened」と「Closed」は、完全に開いたときまたは完全に閉じたときにモーターを停止します。これらは、外部 (たとえば、他のステート マシン) に「ドアが開いている」または「ドアが閉じている」という状況を知らせます。

ミーリーマシン

FSM は入力アクションも使用します。つまり、出力は入力と状態に依存します。Mealy FSM を使用すると、多くの場合、状態数が削減されます。図 7 の例は、Moore の例と同じ動作を実装する Mealy FSM を示しています (動作は実装された FSM 実行モデルに依存し、たとえば仮想 FSMでは機能しますが、イベント駆動型 FSMでは機能しません)。入力アクション (I:) は 2 つあります。「command_close が到着したらモーターを始動してドアを閉める」と「command_open が到着したらモーターを反対方向に始動してドアを開ける」です。「開く」と「閉める」の中間状態は示されていません。

シーケンサー（ジェネレーターとも呼ばれる）は、1文字の入力アルファベットを持つアクセプタとトランスデューサーのサブクラスです。これらは1つのシーケンスのみを生成します。これは、アクセプタまたはトランスデューサーの出力シーケンスとして見ることができます。^[6]

さらに、決定性( DFA ) オートマトンと非決定性( NFA、GNFA ) オートマトンを区別します。決定性オートマトンでは、すべての状態は、可能な入力ごとに 1 つの遷移を持ちます。非決定性オートマトンでは、入力によって、特定の状態に対して 1 つの遷移、複数の遷移、または遷移なしが発生する可能性があります。べき乗集合構築アルゴリズムは、任意の非決定性オートマトンを、同じ機能を持つ (通常はより複雑な) 決定性オートマトンに変換できます。

1 つの状態のみを持つ有限状態マシンは「組み合わせ FSM」と呼ばれます。これは、状態への遷移時にのみアクションを許可します。この概念は、複数の有限状態マシンを連携させる必要がある場合や、設計ツールに合わせて純粋に組み合わせ的な部分を FSM の形式として考えることが便利な場合に便利です。^[12]

ステートマシンを表現するために利用できるセマンティクスのセットは他にもあります。たとえば、組み込みコントローラのロジックをモデリングおよび設計するためのツールがあります。^[13]これらは、階層型ステートマシン（通常は複数の現在の状態を持つ）、フローグラフ、および真理値表を1 つの言語に組み合わせて、異なる形式とセマンティクスのセットを生み出します。^{[14]これらのチャートは、} Harel のオリジナルのステートマシン と同様に、 ^[15]階層的にネストされた状態、直交領域、状態アクション、および遷移アクションをサポートします。^[16]

一般的な分類に従って、次のような正式な定義が見つかります。

決定論的有限状態マシンまたは決定論的有限状態アクセプタは、次の5 つの要素で構成され ます。 ${\displaystyle (\Sigma ,S,s_{0},\delta ,F)}$

• ${\displaystyle \Sigma }$入力アルファベット（有限の空でない記号の集合）です。
• ${\displaystyle S}$有限の空でない状態の集合である。
• ${\displaystyle s_{0}}$は初期状態であり、 の要素です。${\displaystyle S}$
• ${\displaystyle \delta}$は状態遷移関数です。(非決定性有限オートマトンでは となり、つまり状態のセットを返します)。${\displaystyle \delta :S\times \Sigma \rightarrow S}$${\displaystyle \delta :S\times \Sigma \rightarrow {\mathcal {P}}(S)}$${\displaystyle \delta}$
• ${\displaystyle F}$は最終状態の集合であり、 の（空の可能性のある）サブセットです。${\displaystyle S}$

決定論的FSMと非決定論的 FSM の両方において、 が部分関数 になることを許容するのが慣例です。つまり、 とのすべての組み合わせに対して が定義される必要はありません。FSM が状態 にある場合、次のシンボルは であり、が定義されていないため、 はエラーを通知できます (つまり、入力を拒否します)。これは一般的な状態マシンの定義には役立ちますが、マシンを変換するときにはあまり役に立ちません。一部のアルゴリズムは、デフォルト形式では全関数を必要とする場合があります。 ${\displaystyle \delta}$${\displaystyle \delta (s,x)}$${\displaystyle s\in S}$${\displaystyle x\in \Sigma }$${\displaystyle M}$${\displaystyle s}$${\displaystyle x}$${\displaystyle \delta (s,x)}$${\displaystyle M}$

有限状態機械は、ヘッドが「読み取り」操作のみを実行し、常に左から右に移動するように制限されたチューリングマシンと同じ計算能力を持っています。つまり、有限状態機械によって受け入れられるすべての形式言語は、そのような種類の制限されたチューリングマシンによって受け入れられ、その逆も同様です。^[17]

有限状態トランスデューサは、次の6 組 です。 ${\displaystyle (\Sigma ,\Gamma ,S,s_{0},\delta ,\omega )}$

• ${\displaystyle \Sigma }$入力アルファベット（有限の空でない記号の集合）です。
• ${\displaystyle \ガンマ}$出力アルファベット（有限の空でない記号の集合）です。
• ${\displaystyle S}$有限の空でない状態の集合である。
• ${\displaystyle s_{0}}$は初期状態であり、 の要素です。${\displaystyle S}$
• ${\displaystyle \delta}$状態遷移関数です: ;${\displaystyle \delta :S\times \Sigma \rightarrow S}$
• ${\displaystyle \omega}$出力関数です。

出力関数が状態と入力シンボル ( ) に依存する場合、その定義はMealy モデルに対応し、Mealy マシンとしてモデル化できます。出力関数が状態 ( ) のみに依存する場合、その定義はMoore モデルに対応し、Moore マシンとしてモデル化できます。出力関数をまったく持たない有限状態マシンは、セミオートマトンまたは遷移システムと呼ばれます。 ${\displaystyle \omega :S\times \Sigma \rightarrow \Gamma }$${\displaystyle \omega :S\rightarrow \Gamma }$

ムーアマシンの最初の出力シンボルを無視すると、すべてのミーリー遷移の出力関数（つまり、すべてのエッジにラベルを付ける）を、宛先のムーア状態の出力シンボルで設定することで、出力が同等のミーリーマシンに簡単に変換できます。ミーリーマシンの状態は、その入力遷移（エッジ）に異なる出力ラベルを持つ可能性があるため、逆の変換はそれほど簡単ではありません。そのような状態はすべて、すべての入力出力シンボルごとに1つずつ、複数のムーアマシン状態に分割する必要があります。^[18]${\displaystyle \omega (s_{0})}$

FSMを最適化するということは、同じ機能を実行する最小の状態数を持つマシンを見つけることを意味します。これを行う最も高速な既知のアルゴリズムは、ホップクロフト最小化アルゴリズムです。^{[19] [20]}その他の手法には、含意テーブルの使用やムーア削減手順などがあります。^{[21]さらに、非巡回FSAは}線形時間で最小化できます。^[22]

デジタル回路では、プログラマブル ロジック デバイス、プログラマブル ロジック コントローラ、ロジック ゲート、フリップフロップまたはリレーを使用して FSM を構築できます。具体的には、ハードウェア実装には、状態変数を格納するレジスタ、状態遷移を決定する組み合わせロジックのブロック、および FSM の出力を決定する 2 番目の組み合わせロジックのブロックが必要です。典型的なハードウェア実装の 1 つは、リチャーズ コントローラです。

メドベージェフマシンでは、出力は状態フリップフロップに直接接続されており、フリップフロップと出力間の時間遅延が最小限に抑えられています。^{[23] [24]}

低電力ステートマシンの状態エンコーディングにより、電力消費を最小限に抑えるように最適化できます。

有限状態マシンを使用してソフトウェア アプリケーションを構築する場合、次の概念が一般的に使用されます。

• オートマトンベースのプログラミング
• イベント駆動型有限状態マシン
• 仮想有限状態マシン
• 状態設計パターン

有限オートマトンは通常、プログラミング言語コンパイラのフロントエンドで使用されます。このようなフロントエンドは、字句解析器とパーサーを実装する複数の有限状態マシンで構成される場合があります。字句解析器は、文字列から始めて、言語トークン（予約語、リテラル、識別子など）のシーケンスを構築し、パーサーはそれに基づいて構文木を構築します。字句解析器とパーサーは、プログラミング言語の文法の通常の部分と文脈自由部分を処理します。^[25]

• サカロヴィッチ、ジャック（2009）。オートマトン理論の要素。フランス語からルーベン・トーマスによる翻訳。ケンブリッジ大学出版局。ISBN 978-0-521-84425-3.ZBL1188.68177  。​
• Wagner, F.、「有限状態マシンによるソフトウェアのモデリング: 実践的アプローチ」、Auerbach Publications、2006 年、ISBN 0-8493-8086-3。 
• ITU-T、勧告 Z.100 仕様および記述言語 (SDL)
• Samek, M.、「C/C++ での実践的なステートチャート」、CMP Books、2002 年、ISBN 1-57820-110-1。 
• Samek, M.、「C/C++ での実践的な UML ステートチャート」、第 2 版、Newnes、2008 年、ISBN 0-7506-8706-1。 
• ガードナー、T.、高度な状態管理、2007年、Wayback Machineで 2008-11-19 にアーカイブ
• Cassandras, C.、Lafortune, S.、「離散イベント システム入門」。Kluwer、1999 年、ISBN 0-7923-8609-4。 
• ティモシー・カム『有限状態機械の合成：機能最適化』Kluwer Academic Publishers、ボストン 1997、ISBN 0-7923-9842-4 
• Tiziano Villa、「有限状態機械の合成: 論理最適化」、Kluwer Academic Publishers、ボストン、1997 年、ISBN 0-7923-9892-0 
• Carroll, J., Long, D.,有限オートマトン理論と形式言語入門。Prentice Hall、Englewood Cliffs、1989年。
• Kohavi, Z.、「スイッチングと有限オートマトン理論」、McGraw-Hill、1978 年。
• Gill, A.,有限状態機械理論入門。McGraw-Hill、1962年。
• ギンズバーグ、S.、「数学機械理論入門」、アディソン・ウェズレー、1962年。

• アービブ、マイケル A. (1969)。抽象オートマトン理論（第 1 版）。ニュージャージー州エングルウッド クリフス: Prentice-Hall, Inc. ISBN 978-0-13-913368-8。
• Bobrow, Leonard S.; Arbib, Michael A. (1974).離散数学: コンピュータと情報科学のための応用代数(第 1 版). フィラデルフィア: WB Saunders Company, Inc. ISBN 978-0-7216-1768-8。
• Booth, Taylor L. (1967)。『Sequential Machines and Automata Theory (第 1 版)』。ニューヨーク: John Wiley and Sons, Inc. 米国議会図書館カードカタログ番号 67-25924。
• Boolos, George; Jeffrey, Richard (1999) [1989]. Computability and Logic (第3版). ケンブリッジ、イギリス: Cambridge University Press. ISBN 978-0-521-20402-6。
• Brookshear, J. Glenn (1989)。計算理論: 形式言語、オートマトン、複雑性。カリフォルニア州レッドウッドシティ: Benjamin/Cummings Publish Company, Inc. ISBN 978-0-8053-0143-4。
• デイビス、マーティン、シガル、エレイン・J・ワイユカー (1994)。計算可能性、複雑性、言語と論理: 理論計算機科学の基礎(第 2 版)。サンディエゴ: アカデミック プレス、ハーコート、ブレイス & カンパニー。ISBN 978-0-12-206382-4。
• ホップクロフト、ジョン E.、ウルマン、ジェフリー D. (1979)。オートマトン理論、言語、計算入門(第 1 版)。アディソン ウェスレー。ISBN 0-201-02988-X。（印刷障害のある利用者も利用可能）
• ホップクロフト、ジョン E. ;モトワニ、ラジーブ;ウルマン、ジェフリー D. (2006) [1979].オートマトン理論、言語、計算入門(第 3 版). Addison-Wesley. ISBN 0-321-45536-3。
• ホプキン、デイビッド。バーバラ、モス (1976)。オートマトン。ニューヨーク: エルゼビア ノースホランド。ISBN 978-0-444-00249-5。
• コゼン、デクスター C. (1997)。オートマトンと計算可能性(第 1 版)。ニューヨーク: Springer-Verlag。ISBN 978-0-387-94907-9。
• Lewis, Harry R. ; Papadimitriou, Christos H. (1998)。『計算理論の要素』（第 2 版）。ニュージャージー州アッパーサドルリバー：Prentice- Hall。ISBN 978-0-13-262478-7。
• リンツ、ピーター (2006)。形式言語とオートマトン(第 4 版)。マサチューセッツ州サドベリー: ジョーンズ アンド バートレット。ISBN 978-0-7637-3798-6。
• ミンスキー、マービン (1967)。『計算：有限マシンと無限マシン』（第 1 版）。ニュージャージー：プレンティス ホール。
• パパディミトリウ、クリストス(1993)。計算複雑性(第 1 版)。アディソン ウェスリー。ISBN 978-0-201-53082-7。
• ピッペンガー、ニコラス (1997)。計算可能性の理論(第 1 版)。ケンブリッジ、イギリス: ケンブリッジ大学出版局。ISBN 978-0-521-55380-3。
• ロジャー、スーザン、フィンリー、トーマス (2006)。JFLAP : 対話型形式言語およびオートマトン パッケージ(第 1 版)。マサチューセッツ州サドベリー: ジョーンズ アンド バートレット。ISBN 978-0-7637-3834-1。
• シプサー、マイケル (2006)。『計算理論入門』（第 2 版）。ボストン、マサチューセッツ州: トムソン コース テクノロジー。ISBN 978-0-534-95097-2。
• ウッド、デリック(1987)。計算理論(第 1 版)。ニューヨーク: Harper & Row、Publishers、Inc. ISBN 978-0-06-047208-5。

• Gurevich, Yuri (2000 年 7 月). 「シーケンシャル抽象ステートマシンによるシーケンシャルアルゴリズムの取得」(PDF) . ACM Transactions on Computational Logic . 1 (1): 77–111. CiteSeerX  10.1.1.146.3017 . doi :10.1145/343369.343384. S2CID  2031696.

• ミッチェル、トム M. (1997)。機械学習(第 1 版)。ニューヨーク: WCB/McGraw-Hill Corporation。ISBN 978-0-07-042807-2。

• Booth, Taylor L. (1967)。『Sequential Machines and Automata Theory (第 1 版)』。ニューヨーク: John Wiley and Sons, Inc. 米国議会図書館カードカタログ番号 67-25924。
• ブース、テイラー L. (1971)。デジタルネットワークとコンピュータシステム (第 1 版)。ニューヨーク: John Wiley and Sons, Inc. ISBN 978-0-471-08840-0。
• McCluskey, EJ (1965)。スイッチング回路理論入門（第 1 版）。ニューヨーク：McGraw-Hill Book Company, Inc. 米国議会図書館カードカタログ番号 65-17394。
• Hill, Fredrick J.; Peterson, Gerald R. (1965)。スイッチング回路理論入門（第 1 版）。ニューヨーク：McGraw-Hill Book Company。米国議会図書館カードカタログ番号 65-17394。

「マルコフ連鎖は、一連の状態s ₁、s ₂、…、s _{r を}連続的に移動するプロセスと考えることができます。…状態s _iにある場合は、確率p _ijで次の停止状態s _jに移動します。これらの確率は、遷移行列の形式で表すことができます。」 (Kemeny (1959)、p. 384)

有限マルコフ連鎖過程は有限型のサブシフトとも呼ばれます。

• Booth, Taylor L. (1967)。『Sequential Machines and Automata Theory (第 1 版)』。ニューヨーク: John Wiley and Sons, Inc. 米国議会図書館カードカタログ番号 67-25924。
• Kemeny, John G.; Mirkil, Hazleton; Snell, J. Laurie; Thompson, Gerald L. (1959)。有限数学構造（第 1 版）。イングルウッド クリフス、ニュージャージー州: Prentice-Hall, Inc. 米国議会図書館カード ​​カタログ番号 59-12841。第 6 章「有限マルコフ連鎖」。

• 有限ステートマシンを使用したシンプルな AI 動作のモデリング ビデオゲームでの使用例
• 有限状態機械のコンピューティングに関する無料オンライン辞書の説明
• NIST アルゴリズムとデータ構造辞書における有限状態機械の説明
• Mealy、Moore、Harel、UML ステート マシンの理論的側面を比較しながら、ステート マシンの種類の簡単な概要を説明します。