有限オートマトン
有限オートマトン(ゆうげんオートマトン、finite automaton)または有限状態機械(ゆうげんじょうたいきかい、finite state machine, FSM)とは、有限個の状態と遷移と動作の組み合わせからなる数学的に抽象化された「ふるまいのモデル」である。デジタル回路やプログラムの設計で使われることがあり、ある一連の状態をとったときどのように論理が流れるかを調べることができる。有限個の「状態」のうち1つの状態をとる。ある時点では1つの状態しかとらず、それをその時点の「現在状態」と呼ぶ。何らかのイベントや条件によってある状態から別の状態へと移行し、それを「遷移」と呼ぶ。それぞれの現在状態から遷移しうる状態と、遷移のきっかけとなる条件を列挙することで定義される。
有限オートマトンは様々な問題に応用でき、半導体設計の自動化、通信プロトコル設計、構文解析などの工学面での応用がある。生物学や人工知能研究では状態機械(群)を使って神経系をモデル化し、言語学では自然言語の文法をモデル化したりする。
状態は、システムの振る舞いのノードであり、システム内で遷移を実行するトリガーを待っている。一般に状態は、同じトリガーに対してシステムの反応が常に同じではない場合に導入される。例えば、カーラジオのシステムでは、特定のラジオ局の放送を聴いている状態で「次へ」というトリガーは次のラジオ局(の放送受信)への移行を意味する。しかし、CDプレーヤーのシステムでは、「次へ」は次のトラックへの移行を意味する。これらは、同じトリガーであっても現在状態によって異なる動作を引き起こす。一部の有限オートマトンの表現では、次のように動作と状態を対応付けることもある。
開始動作: その状態に入るときに行う動作
終了動作: その状態から出るときに行う動作
遷移は、条件が満たされたときまたはイベントを受信したときに実行される動作の集合である。
有限オートマトンについてその振る舞いを直接的に、状態をノード(節)とし遷移をエッジ(辺あるいは矢印)とした、ネットワーク構造(グラフ理論・グラフ (データ構造) )の図にしたものが状態遷移図である。
有限オートマトンについて、その遷移規則(関数)を表にしたものが状態遷移表である。現在の状態(例えばB)と入力(例えばY)の交差するところに次の状態(例えばC)を示す。以下にごく単純な一例を示す。
統一モデリング言語(UML)には状態機械(ステートマシン)を記述するための豊富な意味論と記法がある。UMLの状態遷移図は従来の有限オートマトンの主な利点を踏襲しつつ、その欠点を克服している。大きな拡張としては、状態の階層化や直交状態の導入があり、動作の記法も拡張されている。ミーリ・マシンもムーア・マシンも記述できる。ミーリ・マシンのように状態だけでなく、イベント(入力)をきっかけとして遷移するようにも書けるし、ムーア・マシンのように遷移ではなく状態と開始動作や終了動作を対応付けることもできる。
仕様及び記述言語(SDL) はITUの標準規格であり、遷移の際の以下のような動作を表す記号を定義している。
SDLには、Abstract Data Types と呼ばれる基本データ型、動作言語、有限状態機械を実行可能にするための実行意味論を埋め込む。
有限オートマトンには他にも様々な表現方法があり、例えば図3もその一種である。
ここで示しているような反応性システムの設計だけでなく、有限オートマトンは電気工学、言語学、計算機科学、哲学、生物学、数学、論理学など様々な領域で利用される。有限オートマトンはオートマトン理論や計算理論で研究される一種のオートマトンである。情報工学や計算機科学では、アプリケーションの動作のモデリング、デジタルシステムのハードウェア設計、ソフトウェア工学、コンパイラ設計、通信プロトコルの設計、計算と言語に関する研究などで幅広く活用されている。
タイプによって、いくつかの定義が存在する。
アクセプタ有限オートマトンは ⟨Σ, S, s0, δ, F⟩ の5要素から構成される。
Σ は入力文字セット(有限だが空ではないシンボルの集合)
S は有限であって空でない状態の集合
s0 は S の要素でもある初期状態
δ は状態遷移関数: δ: S × Σ → S (非決定性有限オートマトンの場合、 δ は状態の集合を返すので \delta: S \times \Sigma \rightarrow \mathcal{P}(S) となる)
F は終了状態の集合であり、 S の部分集合(空もありうる)
決定性FSMでも非決定性FSMでも \delta は部分関数でもよく、 \delta(q, x) としたとき、q \isin S と x \isin \Sigma のあらゆる組合せについて定義する必要はない。有限オートマトン M が q という状態で次の入力記号が x のとき、\delta(q, x) が未定義なら M はエラーを返す(すなわち、入力は拒絶・却下される)。これは汎用の状態機械の定義では便利だが、状態機械を変換するのにはあまり便利ではない。デフォルトの形式では全体関数であることを要求するアルゴリズムも存在する。
有限状態機械は制限されたチューリングマシンと見ることもでき、ヘッドが読み取り動作しかできず、常に左から右へと読み取っていくチューリングマシンと言える。
トランスデューサ有限オートマトンは ⟨Σ, Γ, S, s0, δ, ω⟩ の6要素から構成される。
Σ は入力文字セット(有限だが空ではないシンボルの集合)
Γ は出力文字セット(有限だが空ではないシンボルの集合)
S は有限であって空でない状態の集合
s0 は S の要素でもある初期状態(非決定性有限オートマトンの場合は初期状態の集合)
δ は状態遷移関数: δ: S × Σ → S
ω は出力関数
出力関数が状態と入力文字の関数 (ω: S × Σ → Γ ) ならば、その定義はミーリ・モデルであり、ミーリ・マシンとしてモデル化できる。出力関数が状態のみに依存する (ω: S → Γ ) ならば、その定義はムーア・モデルであり、ムーア・マシンとしてモデル化できる。出力機能のない有限オートマトンは状態遷移系などと呼ばれる。
ムーア・マシンの最初の出力シンボル \omega (s_0) を無視すれば、ミーリ・マシンで遷移ごとに遷移先のムーア・マシンの状態の出力シンボルを出力するよう出力関数を設定すれば、ミーリ・マシンに容易に変換できる。ミーリ・マシンの状態はそこに遷移してくる矢印ごとに異なる出力ラベルが設定されているため、逆の変換はそれほど単純ではない。その場合は、出力シンボルごとに状態を設定してやる必要がある。
有限オートマトンの最適化とは、同じ機能を実現するのに必要とされる状態の数をいかに減らすかを意味する。既知の最速のアルゴリズムとして Hopcroft minimization algorithm がある。他にも Implication table や Moore reduction procedure といった手法が使われる。また、非環状FSAは線型時間で最小化できる。
デジタル回路では、プログラマブルロジックデバイス、プログラマブルロジックコントローラ、論理ゲート、フリップフロップ、リレーなどを使って有限オートマトンが構成される。もっと具体的に言えば、状態を格納するレジスタを持ち、状態遷移を決定する論理回路と出力を決定する論理回路を持つハードウェアが有限オートマトンであると言える。初期のハードウェア実装として Richards controller がある。
フリップフロップと出力の間には伝播遅延が存在するため、ミーリ・マシンやムーア・マシンからは非同期出力の論理回路が生成される。このため動作周波数が遅くなってしまう。ミーリ・マシンやムーア・マシンはフリップフロップから直接出力する形に変換でき、そうすることで動作周波数を高めることができる。このように変換した有限状態機械を Medvedev FSM と呼ぶことがある。その最も単純な例としてカウンタ回路がある。
有限オートマトンを使ったソフトウェアアプリケーションを作るのに以下のコンセプトが一般に使われる。