有限状態機械

オートマタのクラス

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

状態機械の挙動は、現代社会の多くの機器で観察できます。これらの機器は、提示される一連のイベントに応じて、あらかじめ決められた一連の動作を実行します。簡単な例としては、適切な組み合わせの硬貨が投入されると商品が出てくる自動販売機、乗客が要求した階数によって停止順序が決まるエレベーター、車が待機しているときに信号が変わる信号機、そして正しい順序で一連の数字を入力する必要があるダイヤル錠などがあります。

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

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

ターンスタイルは状態機械として考えられ、ロック状態とロック解除状態の2 つの状態があります。^{[ 7 ]}その状態に影響を与える入力は 2 つあります。スロットにコインを入れる ( coin ) とアームを押す ( push ) です。ロック状態では、アームを押しても効果はありません。入力pushを何度与えても、ロック状態のままです。コインを入れる、つまり機械にコインを入力すると、状態がロック状態からロック解除状態に切り替わります。ロック解除状態では、追加のコインを入れても効果はありません。つまり、追加のコインを入力しても状態は変わりません。顧客がアームを押して通過すると、push入力が与えられ、状態がロック状態にリセットされます。

回転式改札機の状態遷移機械は、状態遷移表で表すことができ、各状態について、機械に与えられた入力に基づいて状態間の遷移と、各入力から生じる出力が示されます。

回転式改札機の状態遷移図は、状態図と呼ばれる有向グラフ（上図）で表すこともできます。各状態はノード（円）で表され、エッジ（矢印）は状態間の遷移を示します。各矢印には、その遷移を引き起こす入力がラベル付けされています。状態変化を引き起こさない入力（例えば、ロック解除状態でのコイン入力）は、元の状態に戻る円形の矢印で表されます。黒い点からロックノードに向かう矢印は、それが初期状態であることを示しています。

状態とは、遷移の実行を待っているシステムの状況を表すものです。遷移とは、条件が満たされたとき、またはイベントが受信されたときに実行される一連のアクションのことです。例えば、オーディオシステムでラジオを聴いているとき（システムは「ラジオ」状態）、次の刺激を受信すると次の放送局に切り替わります。システムが「CD」状態にあるときは、次の刺激によって次のトラックに切り替わります。同じ刺激でも、現在の状態によって異なるアクションがトリガーされます。

有限状態機械の表現によっては、状態に動作を関連付けることも可能である。

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

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

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

アクセプター

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

形式言語と呼ばれる記号列の集合（無限である可能性もある）は、その集合を正確に受理する受理器が存在する場合に正規言語である。 ^{[ 13 ]}例えば、偶数個のゼロを含むバイナリ文字列の集合は正規言語であるが（図5参照）、長さが素数であるすべての文字列の集合は正規言語ではない。^{[ 14 ]}

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

与えられたアクセプタによって受け入れられる言語を決定する問題は、代数的経路問題の一例であり、それ自体は、(任意の)半環の要素によって重み付けされたエッジを持つグラフへの最短経路問題の一般化である。^{[ 15 ] [ 16 ]}

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

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

トランスデューサー

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

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

ムーアマシン

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

ミーリーマシン

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

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

一般的な分類に従って、以下の正式な定義が見出される。

決定論的有限状態機械または決定論的有限状態アクセプタは五つ組である${\displaystyle (\Sigma ,S,s_{0},\delta ,F)}$、 どこ：

• ${\displaystyle \Sigma }$は入力アルファベット（有限で空でない記号の集合）です。
• ${\displaystyle S}$は、有限で空でない状態の集合である。
• $s0$初期状態、要素${\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の両方において、${\displaystyle \delta }$部分関数である、つまり${\displaystyle \delta (s,x)}$すべての組み合わせに対して定義する必要はありません${\displaystyle s\in S}$そして${\displaystyle x\in \Sigma }$FSMの場合${\displaystyle M}$状態にある${\displaystyle s}$次のシンボルは${\displaystyle x}$そして${\displaystyle \delta (s,x)}$定義されていない場合は、${\displaystyle M}$エラーを通知する（つまり、入力を拒否する）ことができます。これは一般的な状態機械の定義には役立ちますが、機械を変換する際にはあまり役に立ちません。一部のアルゴリズムは、デフォルト形式では全関数を必要とする場合があります。

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

有限状態トランスデューサは六つ組である${\displaystyle (\Sigma ,\Gamma ,S,s_{0},\delta ,\omega )}$、 どこ：

• ${\displaystyle \Sigma }$は入力アルファベット（有限で空でない記号の集合）です。
• ${\displaystyle \Gamma }$は出力アルファベット（有限個の空でない記号の集合）です。
• ${\displaystyle S}$は、有限で空でない状態の集合である。
• $s0$は初期状態であり、${\displaystyle S}$;
• ${\displaystyle \delta }$状態遷移関数は次のとおりです。${\displaystyle \delta :S\times \Sigma \rightarrow S}$;
• ${\displaystyle \omega }$これは出力関数です。

出力関数が状態と入力シンボルに依存する場合（${\displaystyle \omega :S\times \Sigma \rightarrow \Gamma }$) この定義はミーリーモデルに対応し、ミーリーマシンとしてモデル化できます。出力関数が状態のみに依存する場合 (${\displaystyle \omega :S\rightarrow \Gamma }$）この定義はムーアモデルに対応し、ムーアマシンとしてモデル化できます。出力関数をまったく持たない有限状態マシンは、半自動機械または遷移システムとして知られています。

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

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

一般的な

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

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

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

ハードウェアエンジニアリング

状態最小化と順序回路の合成

有限マルコフ連鎖過程

マルコフ連鎖は、状態s ₁ , s ₂ , …, s _rを順に通過していくプロセスと考えることができます。状態s _iにある場合、確率p _ijで次の停止状態である状態s _jへ遷移します。これらの確率は遷移行列の形で表すことができます。

有限マルコフ連鎖過程は、有限型部分シフトとも呼ばれる。