有限オートマトンとは? わかりやすく解説

Weblio 辞書 > 同じ種類の言葉 > 情報 > コンピュータ > オートマトン > 有限オートマトンの意味・解説 

有限オートマトン

(状態機械 から転送)

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2025/06/20 00:18 UTC 版)

オートマトン理論

有限オートマトン(ゆうげんオートマトン、: finite automaton)または有限状態機械 ゆうげんじょうたいきかい、 : finite state machine, FSM)とは、有限個の状態と遷移規則からなる状態機械。

チューリングマシンとは異なり計算状態を記憶するテープを持たず、チューリング完全ではないが、様々な応用がある。

概念と用語

状態(: state)は、システムの振る舞いのノードであり、システム内で遷移(: transition)を実行するトリガーを待っている。一般に状態は、同じトリガーに対してシステムの反応が常に同じではない場合に導入される。例えば、カーラジオのシステムでは、特定のラジオ局の放送を聴いている状態で「次へ」というトリガーは次のラジオ局(の放送受信)への移行を意味する。しかし、CDプレーヤーのシステムでは、「次へ」は次のトラックへの移行を意味する。これらは、同じトリガーであっても現在状態によって異なる動作を引き起こす。一部の有限オートマトンの表現では、次のように動作(: action)と状態を対応付けることもある。

  • 開始(: entry)動作: その状態に入るときに行う動作
  • 終了(: exit)動作: その状態から出るときに行う動作

遷移(: transition)は、条件が満たされたときまたはイベントを受信したときに実行される動作の集合である。

表現

図1 UML状態遷移図の例
図2 SDL ステートマシン図の例
図3 単純な有限オートマトンの例

状態遷移図

有限オートマトンについてその振る舞いを直接的に、状態をノード(節)とし遷移をエッジ(辺あるいは矢印)とした、ネットワーク構造(グラフ理論グラフ (データ構造) )の図にしたものが状態遷移図である。

状態遷移表

有限オートマトンについて、その遷移規則(関数)を表にしたものが状態遷移表である。現在の状態(例えばB)と入力(例えばY)の交差するところに次の状態(例えばC)を示す。以下にごく単純な一例を示す。

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

UMLステートマシン

統一モデリング言語(UML)には状態機械(ステートマシン)を記述するための豊富な意味論と記法がある。UMLの状態遷移図は従来の有限オートマトンの主な利点を踏襲しつつ、その欠点を克服している。大きな拡張としては、状態の階層化や直交状態の導入があり、動作の記法も拡張されている。ミーリ・マシンムーア・マシンも記述できる。ミーリ・マシンのように状態だけでなく、イベント(入力)をきっかけとして遷移するようにも書けるし、ムーア・マシンのように遷移ではなく状態と開始動作や終了動作を対応付けることもできる。

SDLステートマシン

仕様及び記述言語(SDL) はITUの標準規格であり、遷移の際の以下のような動作を表す記号を定義している。

  • イベント送信
  • イベント受信
  • タイマ開始
  • タイマキャンセル
  • 別の並行動作するステートマシンを開始
  • 判断

SDLには、Abstract Data Types と呼ばれる基本データ型、動作言語、有限状態機械を実行可能にするための実行意味論を埋め込む。

他の状態図

有限オートマトンには他にも様々な表現方法があり、例えば図3もその一種である。

用途

ここで示しているような反応性システムの設計だけでなく、有限オートマトンは電気工学言語学計算機科学哲学生物学数学論理学など様々な領域で利用される。有限オートマトンはオートマトン理論や計算理論で研究される一種のオートマトンである。情報工学や計算機科学では、アプリケーションの動作のモデリング、デジタルシステムのハードウェア設計、ソフトウェア工学、コンパイラ設計、通信プロトコルの設計、計算と言語に関する研究などで幅広く活用されている。

分類

図4 アクセプタFSM: "nice"を語句解析する
図5 受容状態の例。この有限オートマトンは入力数列内の"0"の個数が偶数個かどうかを判断する。S1は0が偶数個のときの受容状態である。

有限オートマトンは二種類に分類される。アクセプタ / リコグナイザとトランスデューサである。

アクセプタ / リコグナイザ

このタイプの有限オートマトンは入力を受容(accept)したり、理解(recognize)して、外界に結果を知らせるために状態(state)を使用する。つまり、最終的に受容状態になったかどうかで「はい」または「いいえ」のいずれかを出力として返す。FSMの全状態は受容状態かそうでないかのいずれかである。全入力を処理したとき状態が受容状態なら、その入力は受容されたことになり、さもなくば拒絶 / 却下されたことになる。基本的に入力は記号(または文字)であり、動作(action)は使用されない。図4 に示した例は "nice" という単語を受容する有限オートマトンを示している。この場合、6番だけが受容状態である。

この機械は言語を定義するものとして説明することもできる。その言語とは、その機械が受容する全ての単語から構成され、それ以外の単語を全く含まないもので、そのような言語をその機械が「受容 / 受理」すると称する。定義から、FSM が受理する言語は正規言語であり、逆にある言語を受理する FSM が存在する場合、その言語を正規言語と称する。

初期状態 / 開始状態

初期状態は、一般にどこからも矢印で指されていない状態である[1]

受容状態 / 受理状態

受容状態は、その機械が手続きを成功裡に完了させた状態である。通常、二重丸で表現される。

図5の決定性有限オートマトン (DFA) は2進数の入力が偶数個の 0 を含むときに受容することを示している。S1 は初期状態でもあり、受容状態でもある。この機械は入力数列に"0"が偶数個含まれるときのみ正しく終了したと判定され、0個も偶数なので"0"が全く含まれない数字列も受容される。このDFAが受容する文字列の例としては、ε(空文字列)、1、11、00、010、1010、10110、などなどがある。

トランスデューサ

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

トランスデューサ(変換機、transducer)は、与えられた入力と動作を伴う状態(両方または一方)に基づいて出力を生成する。このタイプの有限オートマトンは計算言語学の分野や制御などに使われる。また、トランスデューサは二種類に分類される。

ムーア・マシン
この有限オートマトンは開始動作のみを使用する。すなわち、出力は状態にのみ依存する。ムーア・モデルの利点はふるまいを単純化できることである。図6の例はエレベーターの扉についてのムーア・マシンを示している。この有限オートマトンは「開放命令」と「閉鎖命令」というふたつの命令を理解し、それによって状態が変化する。「開放途中」状態にある開始動作(E:)は扉の開くところを監視し始めることを示し、「閉鎖途中」状態にある開始動作(E:)は扉の閉じるところを監視し始めることを意味する。「開放」と「閉鎖」状態は動作を伴わないが、これらは外界(つまり他のオートマトン)に扉が開いているとか閉まっているといった状況を知らせる意味を持つ。
ミーリ・マシン
この有限オートマトンは入力動作のみを使用する。すなわち、出力は入力と状態に依存する。ミーリ・モデルは状態の数を減らす作用がある。図7の例はムーア・マシンの例と同じものをミーリ・マシンで実装したものを示している(実装された有限オートマトンのふるまいは実行モデルに依存する。例えば仮想有限状態機械英語版では動作するが、イベント駆動有限状態機械英語版では動作しない)。これは二つの入力動作を持つ。「閉鎖命令が来たら扉を閉めるためにモーターを起動する」という入力動作と「開放命令が来たら扉を開けるためにモーターを起動する」という入力動作である。

実際には、これらを混合したモデルがよく使用される。

ムーア・モデルとミーリ・モデルの違いの詳細は、実施例も含めて外部サイトの"Moore or Mealy model?"にある(ただし英語)。

決定性

さらなる分類方法として、決定性有限オートマトン (DFA) と非決定性有限オートマトン (NFA, GNFA) がある。決定性有限オートマトンでは、各状態の考えられる全ての入力について一意に次の状態が決定される。非決定性有限オートマトンでは、ある状態にある入力があったとき遷移がどうなるかが決定されない(遷移がないかもしれないし、複数の遷移が対応しているかもしれない)。このような区別は実行時間などの観点では重要だが、ふるまいに関する観点ではそれほど重要ではない。それぞれのオートマトンで表現可能なふるまいは同じであり、任意のNFAを等価な(しかしより大きな)DFAに変換するアルゴリズムが存在する(冪集合構築英語版)。

ひとつしか状態を持たない有限オートマトンは結合有限オートマトンと呼ばれ、入力動作のみを持つ。これは複数の有限オートマトンが協調動作する場合に便利であり、結合有限オートマトンとして表せる部分を抽出して設計に活用する。


数学モデル

タイプによって、いくつかの定義が存在する。 アクセプタ有限オートマトンは ⟨Σ, S, s0, δ, F⟩ の5要素から構成される。





有限オートマトンと同じ種類の言葉


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「有限オートマトン」の関連用語

有限オートマトンのお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



有限オートマトンのページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの有限オートマトン (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2025 GRAS Group, Inc.RSS