有限状態マシン

フリー百科事典ウィキペディアより
ナビゲーションにジャンプ 検索にジャンプ

Combinational logicFinite-state machinePushdown automatonTuring machineAutomata theoryオートマトン理論.svg
この画像について
オートマトンのクラス
(各レイヤーをクリックすると、そのテーマに関する記事が表示されます)

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

ステート マシンの動作は、提示された一連のイベントに応じて所定の一連のアクションを実行する、現代社会の多くのデバイスで観察できます。簡単な例としては、硬貨の適切な組み合わせが投入されたときに製品を販売する自動販売機、乗客が要求した階数によって停止の順序が決定されるエレベーター、かごが待っているときに順序を変更する信号機、必要な組み合わせのロックが挙げられます。適切な順序での一連の数字の入力。

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

例: コイン式改札機

改札口の状態図
改札口

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

ステート マシンと見なされる回転式改札口には、 LockedUnlockedの 2 つの状態があります。[4]その状態に影響を与える可能性のある入力は 2 つあります。コインをスロットに入れる ( coin ) と、アームを押す ( push ) です。ロック状態では、アームを押しても効果はありません。何度入力プッシュしてもロック状態のままです。コインを入れる (つまり、マシンにコインを入力する) と、状態がLockedからUnlockedに変わります。ロックが解除された状態では、追加のコインを入れても効果はありません。つまり、追加のコインを与える入力は状態を変更しません。ただし、お客様が腕を押してプッシュ入力を行うと、状態はLockedに戻ります。

回転式改札口のステート マシンは、可能な状態ごとに、それらの間の遷移 (マシンに与えられた入力に基づく) と、各入力から生じる出力を示す 状態遷移表で表すことができます。

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

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

概念と用語

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

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

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

表現

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

状態/イベント テーブル

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

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

UML ステート マシン

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

SDL ステート マシン

Specification and Description LanguageITUの標準であり、移行中のアクションを説明するためのグラフィカル シンボルが含まれています。

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

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

その他の状態図

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

使い方

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

分類

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

アクセプター

図 4: アクセプター FSM: 文字列 "nice" の解析。
図 5: アクセプターの表現。この例は、2 進数に偶数の 0 があるかどうかを判断する例を示しています。ここで、S 1受け入れ状態であり、S 2非受け入れ状態です。

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

形式言語と呼ばれる (おそらく無限の) シンボル シーケンスのセットは、そのセットを正確に受け入れるアクセプターが存在する場合通常の言語です。たとえば、偶数個のゼロを含むバイナリ文字列のセットは通常の言語ですが (図 5 を参照)、長さが素数であるすべての文字列のセットはそうではありません。[7] : 18, 71 

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

特定のアクセプターによって受け入れられる言語を決定する問題は、代数経路問題のインスタンスです。それ自体が、(任意の) 半の要素によって重み付けされたエッジを持つグラフへの最短経路問題の一般化です[8] [9] [専門用語]

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

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

分類子

分類子は、 nが厳密に 2 より大きいn項の出力を生成するアクセプターの一般化です。[10]

トランスデューサー

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

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

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

ムーア機
FSM はエントリ アクションのみを使用します。つまり、出力は状態のみに依存します。ムーア モデルの利点は、動作が単純化されることです。エレベーターのドアを考えてみましょう。ステート マシンは、状態の変更をトリガーする「command_open」と「command_close」の 2 つのコマンドを認識します。状態 "Opening" のエントリ アクション (E:) はドアを開くモーターを開始し、状態 "Closeing" のエントリ アクションはドアを閉じる反対方向のモーターを開始します。「開」と「閉」の状態は、全開または全閉でモーターを停止します。これらは、「ドアが開いている」または「ドアが閉じている」という状況を外の世界 (たとえば、他のステート マシン) に通知します。
ミーリーマシン
FSM は入力アクションも使用します。つまり、出力は入力と状態に依存します。Mealy FSM を使用すると、多くの場合、状態数が減少します。図 7 の例は、Moore の例と同じ動作を実装する Mealy FSM を示しています (動作は実装された FSM 実行モデルに依存し、たとえば、仮想 FSMでは機能しますが、イベント駆動型 FSMでは機能しません)。2 つの入力アクション (I:) があります。「command_close が到着した場合、モーターを開始してドアを閉じます」と「command_open が到着した場合、モーターを反対方向に開始してドアを開きます」。「開」と「閉」の中間状態は示されていません。

シーケンサー

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

決定論

さらに、決定論的( DFA )オートマトンと非決定論的( NFAGNFA ) オートマトンが区別されます。決定論的オートマトンでは、すべての状態は可能な入力ごとに 1 つの遷移を持ちます。非決定性オートマトンでは、入力によって、特定の状態の遷移が 1 つ、複数、または遷移しない可能性があります。パワーセット構築アルゴリズムは、任意の非決定性オートマトンを、同一の機能を持つ (通常はより複雑な) 決定性オートマトンに変換できます。

状態が 1 つしかない有限状態マシンは、「組み合わせ FSM」と呼ばれます。状態への遷移時にのみアクションを許可しますこの概念は、多数の有限状態マシンが連携して動作する必要がある場合や、設計ツールに合わせて純粋な組み合わせパーツを FSM の形式と見なすことが便利な場合に役立ちます。[11]

代替セマンティクス

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

数学的モデル

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

決定論的有限状態マシンまたは決定論的有限状態アクセプター5 倍です。 、 どこ:

  • 入力アルファベット(有限の空でない記号の集合) です。
  • 空でない状態の有限集合です。
  • の要素である初期状態です。;
  • は状態遷移関数です。(非決定性有限オートマトンでは、、つまり状態のセットを返します);
  • は最終状態のセットであり、(おそらく空の) サブセットです。.

決定論的 FSM と非決定論的 FSM の両方で、部分関数であること、すなわちのすべての組み合わせに対して定義する必要はありません。. FSMの場合状態です、次の記号はが定義されていない場合、エラーを通知できます (つまり、入力を拒否します)。これは、一般的なステート マシンの定義には役立ちますが、マシンの変換時にはあまり役に立ちません。デフォルト形式の一部のアルゴリズムでは、合計関数が必要になる場合があります。

有限ステート マシンは、チューリング マシンと同じ計算能力を持ちます。チューリング マシンは、ヘッドが「読み取り」操作のみを実行できるように制限されており、常に左から右に移動する必要があります。つまり、有限状態マシンによって受け入れられる各形式言語は、そのような種類の制限付きチューリング マシンによって受け入れられ、その逆も同様です。[16]

有限状態変換器六重です 、 どこ:

  • 入力アルファベット(有限の空でない記号の集合) です。
  • 出力アルファベット (有限の空でない記号の集合) です。
  • 空でない状態の有限集合です。
  • の要素である初期状態です。;
  • は状態遷移関数です。;
  • 出力関数です。

出力関数が状態と入力シンボルに依存する場合 () その定義は Mealy モデルに対応し、Mealyマシンとしてモデル化できます出力関数が状態のみに依存する場合 () その定義はムーア モデルに対応し、ムーアマシンとしてモデル化できます出力関数をまったく持たない有限状態機械は、セミオートマトンまたは遷移システムとして知られています。

ムーア マシンの最初の出力シンボルを無視すると、、その後、すべての Mealy 遷移の出力関数を設定する (つまり、すべてのエッジにラベルを付ける) ことにより、出力と同等の Mealy マシンに容易に変換できます。Mealy マシンの状態は、入力遷移 (エッジ) で異なる出力ラベルを持つ場合があるため、逆変換はそれほど単純ではありません。そのような状態はすべて、インシデント出力シンボルごとに 1 つずつ、複数の Moore マシン状態に分割する必要があります。[17]

最適化

FSM の最適化とは、同じ機能を実行する最小数の状態を持つマシンを見つけることを意味します。これを行う最も高速な既知のアルゴリズムは、Hopcroft 最小化アルゴリズムです。[18] [19]他の手法には、含意表またはムーア削減手順の使用が含まれます。[20]さらに、非環状 FSA は線形時間で最小化できます[21]

実装

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

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

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

Medvedev マシンでは、出力はステート フリップフロップに直接接続され、フリップフロップと出力の間の時間遅延が最小限に抑えられます。[22] [23]

低電力ステート マシン のスルーステート エンコーディングは、電力消費を最小限に抑えるために最適化される場合があります。

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

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

有限状態マシンとコンパイラ

有限オートマトンは、プログラミング言語コンパイラのフロントエンドでよく使用されます。このようなフロントエンドは、字句解析器とパーサーを実装するいくつかの有限状態マシンを含む場合があります。文字のシーケンスから開始して、字句アナライザーは、パーサーが構文ツリーを構築する言語トークン (予約語、リテラル、識別子など) のシーケンスを構築します。字句解析器とパーサーは、プログラミング言語の文法の通常部分と文脈自由部分を処理します。[24]

も参照

参考文献

  1. ^ ワン・ジャクン (2019). コンピューター サイエンスの形式的手法CRCプレス。p。34.ISBN _ 978-1-4987-7532-8.
  2. ^ "有限状態マシン - 華麗な数学と科学のウィキ" . 華麗な.org 2018 年4 月 14 日閲覧
  3. ^ ベルザー、ジャック。ホルツマン、アルバート・ジョージ。ケント、アレン(1975)。コンピュータ科学技術の百科事典巻。25. 米国: CRC プレス。p。73.ISBN _ 978-0-8247-2275-3.
  4. ^ a b コッシー、トーマス (2004). アプリケーションによる離散数学アカデミックプレス。p。762.ISBN _ 978-0-12-421180-3.
  5. ^ ライト、デビッド R. (2005). 「有限状態マシン」(PDF) . CSC215 クラスノート. David R. Wright のウェブサイト、N. Carolina State Univ. 2014-03-27に元の(PDF)からアーカイブされました2012 年7 月 14 日閲覧
  6. ^ a b Keller、Robert M. (2001). 「クラシファイア、アクセプター、トランスデューサー、シーケンサー」(PDF) . コンピューター サイエンス: 実装への抽象化(PDF)ハービーマッドカレッジ. p。480。
  7. ^ ジョン・E・ホップクロフトとジェフリー・D・ウルマン (1979). オートマトン理論、言語、および計算の紹介読書/MA: Addison-Wesley. ISBN 978-0-201-02988-8.
  8. ^ ポリー、マーク。Kohlas、Jürg(2011)。ジェネリック推論: 自動化された推論のための統一理論ジョン・ワイリー&サンズ. 第6章パス問題の評価代数、p。特に223。ISBN 978-1-118-01086-0.
  9. ^ Jacek Jonczy (2008 年 6 月). 「代数経路の問題」(PDF) . 2014-08-21のオリジナル(PDF)からのアーカイブ2014 年 8 月20 日閲覧 、p。34
  10. ^ フェルキン、M. (2007). ギエ、ファブリス。ハミルトン、ハワード J. (eds.)。データマイニングにおける品質測定 - 計算知能の研究巻。43. スプリンガー、ベルリン、ハイデルベルク。pp.277–278。ドイ: 10.1007/978-3-540-44918-8_12 . ISBN 978-3-540-44911-9.
  11. ^ Brutscheck, M.、Berger, S.、Franke, M.、Schwarzbacher, A.、Becker, S.: 効率的な IC 分析のための構造分割手順。IET アイルランド信号およびシステム会議、(ISSC 2008)、pp.18–23。2008 年 6 月 18 ~ 19 日、アイルランド、ゴールウェイ。 [1]
  12. ^ 「Tiwari, A. (2002. Simulink Stateflow モデルの正式なセマンティクスと分析方法」(PDF) . sri.com 2018 年4 月 14 日閲覧
  13. ^ Hamon, G. (2005). Stateflow の表示セマンティクス組み込みソフトウェアに関する国際会議。ニュージャージー州ジャージーシティ: ACM. pp.164–172。CiteSeerX 10.1.1.89.8817 . 
  14. ^ "Harel, D. (1987. A Visual Formalism for Complex Systems. Science of Computer Programming, 231–274" (PDF) . 2011-07-15のオリジナル(PDF)からのアーカイブ2011 年6 月 7 日閲覧
  15. ^ "Alur, R., Kanade, A., Ramesh, S., & Shashidhar, KC (2008). Simulink/Stateflow モデルのシミュレーション範囲を改善するためのシンボリック解析. 組み込みソフトウェアに関する国際会議 (pp. 89–98).ジョージア州アトランタ: ACM" (PDF) . 2011 年 7 月 15 日にオリジナル(PDF)からアーカイブされました
  16. ^ ブラック、ポール E (2008 年 5 月 12 日). 「有限状態マシン」 . アルゴリズムとデータ構造のディクショナリ米国国立標準技術研究所2018 年 10 月 13 日にオリジナルからアーカイブされました2016年 11 月 2 日閲覧
  17. ^ アンダーソン、ジェームズ・アンドリュー; 頭、トーマス J. (2006)。現代の応用によるオートマトン理論ケンブリッジ大学出版局。pp.105–108。ISBN 978-0-521-84887-9.
  18. ^ ホップクロフト、ジョン E. (1971). 有限オートマトン(PDF)で状態を最小化するためn log nアルゴリズム(テクニカル レポート)。巻。CS-TR-71-190。スタンフォード大学 永久リンク切れ
  19. ^ アルメイダ、マルコ。モレイラ、ネルマ。レイス、ロジェリオ (2007)。オートマトン最小化アルゴリズムのパフォーマンスについて(PDF) (テクニカル レポート)。巻。DCC-2007-03。ポルト大学 2009 年 1 月 17 日のオリジナル(PDF)からのアーカイブ2008年 6 月 25 日閲覧
  20. ^ エドワード・F・ムーア (1956). CE シャノンと J. マッカーシー (編)。「Gedanken-Sequential Machines の実験」. 数学研究の実録プリンストン大学出版局。34 : 129–153.ここ: 定理 4、p.142。
  21. ^ Revuz、D. (1992). 「線形時間における非巡回オートマトンの最小化」 . 理論計算機科学92 : 181–189. ドイ10.1016/0304-3975(92)90142-3 .
  22. ^ ケスリン、ヒューバート (2008). 「Mealy、Moore、Medvedev タイプおよび組み合わせ出力ビット」 . デジタル集積回路設計: VLSI アーキテクチャから CMOS 製造までケンブリッジ大学出版局。p。787.ISBN _ 978-0-521-88267-5.
  23. ^ 2017 年 1 月 18 日にWayback Machineでアーカイブされたスライド Synchronous Finite State Machines; デザインと行動ハンブルグ応用科学大学、p.18
  24. ^ Aho, Alfred V .; セティ、ラヴィ; ウルマン、ジェフリー D. (1986)。Compilers: Principles, Techniques, and Tools (第 1 版)。アディソン・ウェズリーISBN 978-0-201-10088-4.

さらに読む

一般

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

  • アービブ、マイケル A. (1969)。抽象オートマトンの理論(第 1 版)。Englewood Cliffs, NJ: Prentice-Hall, Inc. ISBN 978-0-13-913368-8.
  • ボブロウ、レナード S.; アービブ、マイケル A. (1974)。離散数学: コンピュータおよび情報科学のための応用代数(第 1 版)。フィラデルフィア: WB Saunders Company, Inc. ISBN 978-0-7216-1768-8.
  • ブース、テイラー L. (1967)。Sequential Machines and Automata Theory (第 1 版)。ニューヨーク: John Wiley and Sons, Inc. Library of Congress カード カタログ番号 67-25924。
  • ブーロス、ジョージ。ジェフリー、リチャード (1999) [1989]。計算可能性と論理(第 3 版)。ケンブリッジ、イギリス: ケンブリッジ大学出版局。ISBN 978-0-521-20402-6.
  • Brookshear、J. Glenn (1989)。計算理論: 形式言語、オートマトン、および複雑性カリフォルニア州レッドウッドシティ: Benjamin/Cummings Publish Company, Inc. ISBN 978-0-8053-0143-4.
  • デイビス、マーティン。シーガル、ロン。Weyuker、Elaine J. (1994)。計算可能性、複雑さ、および言語とロジック: 理論的コンピューター サイエンスの基礎(第 2 版)。サンディエゴ: Academic Press、Harcourt、Brace & Company。ISBN 978-0-12-206382-4.
  • ホプクロフト、ジョン。ウルマン、ジェフリー(1979)。オートマトン理論、言語、および計算の紹介(第 1 版)。ミサを読む:アディソン・ウェズリー。ISBN 978-0-201-02988-8.
  • Hopcroft、ジョン E.; モトワニ、ラジーブ。ウルマン、ジェフリー D. (2001)。オートマトン理論、言語、および計算の紹介(第 2 版)。ミサを読む:アディソン・ウェズリー。ISBN 978-0-201-44124-6.
  • ホプキン、デビッド。モス、バーバラ(1976)。オートマタニューヨーク: Elsevier North-Holland. ISBN 978-0-444-00249-5.
  • Kozen、Dexter C. (1997)。オートマトンと計算可能性(第 1 版)。ニューヨーク:Springer-Verlag。ISBN 978-0-387-94907-9.
  • ルイス、ハリー R .; Papadimitriou、Christos H. (1998)。計算理論の要素(第 2 版)。ニュージャージー州アッパーサドルリバー:プレンティスホール。ISBN 978-0-13-262478-7.
  • リンツ、ピーター(2006)。Formal Languages and Automata (第 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.

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

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

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

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

  • ブース、テイラー L. (1967)。Sequential Machines and Automata Theory (第 1 版)。ニューヨーク: John Wiley and Sons, Inc. Library of Congress カード カタログ番号 67-25924。
  • ブース、テイラー L. (1971)。デジタル ネットワークとコンピュータ システム(第 1 版)。ニューヨーク: John Wiley and Sons, Inc. ISBN 978-0-471-08840-0.
  • マクラスキー、EJ (1965)。スイッチング回路の理論の紹介(第 1 版)。ニューヨーク: McGraw-Hill Book Company, Inc. 米国議会図書館カード ​​カタログ番号 65-17394。
  • ヒル、フレドリック J.; ピーターソン、ジェラルド R. (1965)。スイッチング回路の理論の紹介(第 1 版)。ニューヨーク:McGraw-Hill Book Company。米国議会図書館カード ​​カタログ番号 65-17394。

有限マルコフ連鎖過程

マルコフ連鎖は、一連の状態s 1s 2、…、s rを連続して移動するプロセスと考えることができます。…状態s iにある場合、状態s jの次の停止点に移動します。確率p ij . これらの確率は、遷移行列の形で表すことができます" (Kemony (1959), p. 384)

有限マルコフ連鎖過程は、有限型のサブシフトとしても知られています。

  • ブース、テイラー L. (1967)。Sequential Machines and Automata Theory (第 1 版)。ニューヨーク: John Wiley and Sons, Inc. Library of Congress カード カタログ番号 67-25924。
  • ジョン・G・ケメニー; ミルキル、ヘイズルトン。スネル、J.ローリー。トンプソン、ジェラルド L. (1959)。有限数学的構造(第 1 版)。Englewood Cliffs, NJ: Prentice-Hall, Inc. 米国議会図書館カード ​​カタログ番号 59-12841。第6章「有限マルコフ連鎖」。

外部リンク