有限状態機械

Combinational logicFinite-state machinePushdown automatonTuring machineAutomata theory
オートマトンの種類

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

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

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

例: コイン式改札口

回転式改札口の状態図
回転式改札口

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

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

回転式改札口の状態マシンは、状態遷移表で表すことができます。状態遷移表は、各可能な状態、状態間の遷移（マシンに与えられた入力に基づく）、および各入力から得られる出力を示します。

現在の状態 入力 次の状態 出力
ロックされています コインロック解除顧客が通過できるように回転式改札口のロックを解除します。
押すロックされていますなし
ロック解除 コインロック解除なし
押すロックされていますお客様が通過したら、回転式改札口をロックします。

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

概念と用語

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

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

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

表現

図1 UML状態チャートの例（トースターオーブン）
図2 SDLステートマシンの例
図3 単純な有限状態機械の例

状態/イベントテーブル

状態遷移表にはいくつかの種類があります。最も一般的な表現は以下の通りです。現在の状態（例：B）と入力（例：Y）の組み合わせが次の状態（例：C）を示します。表だけでは動作を完全に記述できないため、脚注を使用するのが一般的です。他の関連する表現では、この制限がない場合があります。例えば、動作の完全な情報を含むFSM定義は、状態表を使用することで可能です（仮想有限状態機械も参照）。

状態遷移表
  現在の状態
入力
状態A状態B状態C
入力X .........
入力Y ...状態C...
入力Z .........

UMLステートマシン

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

SDLステートマシン

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

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

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

その他の状態図

図 3 のような FSM を表すバリアントは多数あります。

使用法

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

分類

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

アクセプター

図 4: アクセプタ FSM: 文字列「nice」の解析。
図 5: アクセプタの表現。この例は、バイナリ数値に 0 が偶数個あるかどうかを判断するアクセプタを示しています。ここで、S 1はアクセプタ状態、S 2は非アクセプタ状態です。

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

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

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

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

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

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

分類器

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

トランスデューサー

図6 トランスデューサFSM: ムーアモデルの例
図7 トランスデューサFSM: Mealyモデルの例

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

制御アプリケーションでは、次の 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つのシーケンスのみを生成し、これはアクセプタまたはトランスデューサーの出力シーケンスとして見ることができます。[ 9 ]

決定論

さらに、決定性オートマトン（DFA）と非決定性オートマトン（NFA、GNFA ）の区別があります。決定性オートマトンでは、各状態は、それぞれの入力に対して正確に1つの遷移を持ちます。非決定性オートマトンでは、入力は、与えられた状態に対して1つの遷移、複数の遷移、または遷移なしのいずれかを引き起こします。べき乗集合構築アルゴリズムは、任意の非決定性オートマトンを、同一の機能を持つ（通常はより複雑な）決定性オートマトンに変換できます。

一つの状態のみを持つ有限状態機械は「組合せFSM」と呼ばれます。これは、ある状態への遷移時にのみアクションを許可します。この概念は、複数の有限状態機械を連携させる必要がある場合や、設計ツールに適合させるために純粋に組合せ的な部分をFSMの一形態として扱うことが都合が良い場合に有用です。[ 15 ]

代替意味論

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

数学モデル

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

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

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

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

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

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

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

出力関数が状態と入力記号（）に依存する場合、その定義はミーリーモデルに対応し、ミーリーマシンとしてモデル化できます。出力関数が状態（ ）のみに依存する場合、その定義はムーアモデルに対応し、ムーアマシンとしてモデル化できます。出力関数を全く持たない有限状態機械は、セミオートマトンまたは遷移システムと呼ばれます。 ω:S×Σ→Γ{\displaystyle \omega :S\times \Sigma \rightarrow \Gamma }ω:S→Γ{\displaystyle \omega :S\rightarrow \Gamma }

ムーアマシンの最初の出力記号を無視すれば、すべてのミーリー遷移の出力関数（すなわち、すべてのエッジにラベルを付ける）に、遷移先のムーア状態の出力記号を設定することで、出力が等価なミーリーマシンに容易に変換できる。ミーリーマシンの状態は、入力される遷移（エッジ）に異なる出力ラベルを持つ可能性があるため、逆変換はそれほど単純ではない。このような状態はすべて、入力される出力記号ごとに1つずつ、複数のムーアマシン状態に分割する必要がある。[ 21 ]ω（s0）{\displaystyle \omega (s_{0})}

最適化

FSMの最適化とは、同じ機能を実行する最小の状態数を持つマシンを見つけることです。これを実行する最も高速な既知のアルゴリズムは、ホップクロフト最小化アルゴリズムです。[ 22 ] [ 23 ]その他の手法としては、含意表の使用やムーア縮約法などがあります。[ 24 ]さらに、非巡回FSAは線形時間で最小化できます。[ 25 ]

実装

ハードウェアアプリケーション

図9 4ビットTTLカウンタの回路図（ステートマシンの一種）

デジタル回路において、FSMはプログラマブルロジックデバイス、プログラマブルロジックコントローラ、論理ゲート、フリップフロップまたはリレーを用いて構築されます。より具体的には、ハードウェア実装には、状態変数を格納するレジスタ、状態遷移を決定する組み合わせロジックブロック、そしてFSMの出力を決定する組み合わせロジックブロックが必要です。

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

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

ソフトウェアアプリケーション

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

有限状態機械とコンパイラ

有限オートマトン（有限オートマトン）は、プログラミング言語コンパイラのフロントエンドでよく使用されます。このようなフロントエンドは、字句解析器と構文解析器を実装する複数の有限状態機械（FSM）で構成される場合があります。字句解析器は文字列から言語トークン（予約語、リテラル、識別子など）の列を構築し、構文解析器はそこから構文木を構築します。字句解析器と構文解析器は、プログラミング言語の文法における正規表現と文脈自由表現の部分を処理します。 [ 28 ]

参照

参考文献

  1. ^ミンスキー（1967）は第2章の冒頭で、有限状態機械と有限オートマトンという代替用語を導入している。
  2. ^王嘉村 (2019).コンピュータサイエンスにおける形式手法. CRC Press. p. 34. ISBN 978-1-4987-7532-8。
  3. ^ 「有限ステートマシン – Brilliant Math & Science Wiki」brilliant.org . 2018年4月14日閲覧。
  4. ^ Lewis & Papadimitriou (1998)、第 2 章: 有限オートマトン。
  5. ^ルイスとパパディミトリウ (1998)、p.  64．
  6. ^ベルツァー, ジャック; ホルツマン, アルバート・ジョージ; ケント, アレン (1975).コンピュータサイエンスとテクノロジー百科事典. 第25巻. 米国: CRC Press. p. 73. ISBN 978-0-8247-2275-3。
  7. ^ a bコシー、トーマス（2004年）『離散数学とその応用』アカデミック・プレス、p. 762、ISBN 978-0-12-421180-3。
  8. ^ Wright, David R. (2005). 「有限ステートマシン」(PDF) . CSC215 授業ノート. David R. Wright ウェブサイト, N. Carolina State Univ.オリジナル(PDF)から2014年3月27日にアーカイブ. 2012年7月14日閲覧.
  9. ^ a b Keller, Robert M. (2001). 「分類器、受容器、トランスデューサ、シーケンサ」(PDF) .コンピュータサイエンス：抽象化から実装まで(PDF) . ハーベイ・マッド・カレッジ. p. 480.
  10. ^ホップクロフト＆ウルマン（1979）、18ページ。
  11. ^ホップクロフト、モトワニ、ウルマン（2006年）、130～131頁。
  12. ^ Pouly, Marc; Kohlas, Jürg (2011). Generic Inference: A Unifying Theory for Automated Reasoning . John Wiley & Sons. 第6章 経路問題のための評価代数、特にp. 223. ISBN 978-1-118-01086-0。
  13. ^ Jacek Jonczy (2008年6月). 「代数的パス問題」(PDF) . 2014年8月21日時点のオリジナル(PDF)からアーカイブ。 2014年8月20日閲覧。、34ページ
  14. ^ Felkin, M. (2007). Guillet, Fabrice; Hamilton, Howard J. (編).データマイニングにおける品質尺度 - 計算知能の研究. 第43巻. Springer, ベルリン, ハイデルベルク. pp.  277– 278. doi : 10.1007/978-3-540-44918-8_12 . ISBN 978-3-540-44911-9。
  15. ^ Brutscheck, M., Berger, S., Franke, M., Schwarzbacher, A., Becker, S.: 効率的なIC解析のための構造分割手順. IET Irish Signals and Systems Conference, (ISSC 2008), pp.18–23. アイルランド、ゴールウェイ、2008年6月18日～19日. [1]
  16. ^ "Tiwari, A. (2002). Simulink Stateflowモデルの形式意味論と解析手法" (PDF) . sri.com . 2018年4月14日閲覧。
  17. ^ Hamon, G. (2005). Stateflow の表示的意味論. 組み込みソフトウェアに関する国際会議. ニュージャージー州ジャージーシティ: ACM. pp.  164– 172. CiteSeerX 10.1.1.89.8817 . 
  18. ^ 「Harel, D. (1987). 複雑系のための視覚的形式主義. コンピュータプログラミングの科学, 231–274」(PDF) . 2011年7月15日時点のオリジナル(PDF)からアーカイブ。 2011年6月7日閲覧。
  19. ^ "Alur, R., Kanade, A., Ramesh, S., & Shashidhar, KC (2008). Symbolic analysis for improved simulation coverage of Simulink/Stateflow models. International Conference on Embedded Software (pp. 89–98). Atlanta, GA: ACM" (PDF) . 2011年7月15日時点のオリジナル(PDF)からのアーカイブ。
  20. ^ Black, Paul E (2008年5月12日). 「有限ステートマシン」 .アルゴリズムとデータ構造の辞書. 米国国立標準技術研究所. 2018年10月13日時点のオリジナルよりアーカイブ。 2016年11月2日閲覧。
  21. ^アンダーソン、ジェームズ・アンドリュー、ヘッド、トーマス・J. (2006).オートマトン理論と現代的応用. ケンブリッジ大学出版局. pp.  105– 108. ISBN 978-0-521-84887-9。
  22. ^ホップクロフト、ジョン（1971）、「有限オートマトンの状態を最小化するn log nアルゴリズム」 、機械と計算の理論、エルゼビア、pp.  189– 196、doi：10.1016 / b978-0-12-417750-5.50022-1、ISBN 978-0-12-417750-5、 2025年9月18日取得{{citation}}: CS1 maint: ISBNによる作業パラメータ（リンク）
  23. ^アルメイダ、マルコ;モレイラ、ネルマ。レイス、ロジェリオ (2007)。オートマトンの最小化アルゴリズムのパフォーマンスについて(PDF) (技術レポート)。 Vol. DCC-2007-03。ポルト大学2009 年 1 月 17 日のオリジナル(PDF)からアーカイブ。2008 年6 月 25 日に取得。
  24. ^ Edward F. Moore (1956). C.E. Shannon, J. McCarthy (編). 「Gedanken-Experiments on Sequential Machines」Annals of Mathematics Studies 34 .プリンストン大学出版局: 129–153 .ここでは、定理 4、p.142 を参照してください。
  25. ^ Revuz, D. (1992). 「線形時間における非巡回オートマトン最小化」.理論計算機科学. 92 : 181–189 . doi : 10.1016/0304-3975(92)90142-3 .
  26. ^ケースリン、ヒューバート (2008). 「ミーリー、ムーア、メドヴェージェフ型および組み合わせ出力ビット」 .デジタル集積回路設計：VLSIアーキテクチャからCMOS製造まで. ケンブリッジ大学出版局. p. 787. ISBN 978-0-521-88267-5。
  27. ^スライドは2017年1月18日にWayback Machineにアーカイブされています、同期有限ステートマシン;設計と動作、ハンブルク応用科学大学、p.18
  28. ^ Aho, Alfred V. ; Sethi, Ravi ; Ullman, Jeffrey D. (1986). Compilers: Principles, Techniques, and Tools (第1版). Addison-Wesley . ISBN 978-0-201-10088-4。

出典

さらに読む

一般的な

理論計算機科学における有限状態機械（オートマトン理論）

  • アービブ, マイケル・A. (1969). 『抽象オートマトン理論』（第1版）. エングルウッド・クリフス, ニュージャージー: プレンティス・ホール社. ISBN 978-0-13-913368-8。
  • ボブロウ、レナード・S.; アービブ、マイケル・A. (1974). 『離散数学：コンピュータと情報科学のための応用代数』（第1版）. フィラデルフィア: WB Saunders Company, Inc. ISBN 978-0-7216-1768-8。
  • Booth, Taylor L. (1967). 『シーケンシャルマシンとオートマトン理論（第1版）』ニューヨーク: John Wiley and Sons, Inc. 米国議会図書館カードカタログ番号 67-25924.
  • ブーロス, ジョージ; ジェフリー, リチャード (1999) [1989].計算可能性と論理（第3版）. ケンブリッジ, イギリス: ケンブリッジ大学出版局. ISBN 978-0-521-20402-6。
  • ブルックシア、J・グレン（1989年）『計算理論：形式言語、オートマトン、そして計算量』カリフォルニア州レッドウッドシティ：ベンジャミン／カミングス出版ISBN 978-0-8053-0143-4。
  • デイビス, マーティン; シーガル, ロン; ウェイユカー, エレイン・J. (1994). 『計算可能性、複雑性、言語と論理：理論計算機科学の基礎』（第2版）. サンディエゴ: アカデミック・プレス, ハーコート・ブレース・アンド・カンパニー. ISBN 978-0-12-206382-4。
  • ホプキン、デイビッド。バーバラ、モス (1976)。オートマトン。ニューヨーク: エルゼビア ノースホランド。ISBN 978-0-444-00249-5。
  • コゼン、デクスター C. (1997)。オートマトンと計算可能性(第 1 版)。ニューヨーク: Springer-Verlag。ISBN 978-0-387-94907-9。
  • ルイス、ハリー・R. ;パパディミトリウ、クリストス・H. (1998). 『計算理論の要素』（第2版）. アッパー・サドル・リバー、ニュージャージー州: プレンティス・ホール. 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版）ニューヨーク：ハーパー・アンド・ロウ出版社ISBN 978-0-06-047208-5。

理論計算機科学における抽象状態機械

有限状態アルゴリズムを用いた機械学習

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

ハードウェア工学：順序回路の状態最小化と合成

  • Booth, Taylor L. (1967). 『シーケンシャルマシンとオートマトン理論（第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.
  • ヒル、フレデリック・J.；ピーターソン、ジェラルド・R.（1965年）『スイッチング回路理論入門』（第1版）ニューヨーク：マグロウヒル社。米国議会図書館カード目録番号65-17394。

有限マルコフ連鎖過程

「マルコフ連鎖とは、状態s 1、s 2、…、s rの集合を連続的に移動するプロセスと考えることができる。…状態s iにある場合、確率p ijで次の状態s jに移行する。これらの確率は遷移行列の形で表すことができる。」（Kemeny (1959)、384ページ）

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

  • Booth, Taylor L. (1967). 『シーケンシャルマシンとオートマトン理論（第1版）』ニューヨーク: John Wiley and Sons, Inc. 米国議会図書館カードカタログ番号 67-25924.
  • ケメニー, ジョン・G.; ミルキル, ヘイズルトン; スネル, J. ローリー; トンプソン, ジェラルド・L. (1959). 『有限数学構造』（第1版）. ニュージャージー州エングルウッド・クリフス: プレンティス・ホール社. 米国議会図書館カード目録番号59-12841.第6章「有限マルコフ連鎖」
「 https://en.wikipedia.org/w/index.php?title=Finite-state_machine&oldid=1323472796#Acceptors_and_recognizers」より取得