有限オートマトン

有限オートマトンとは

有限オートマトンとは有限個の状態と遷移と動作の組み合わせからなる数学的モデルです。
オートマトンはギリシア語の「自動的に動くもの」に由来し、機械仕掛けの人形や動物を意味します。ある目的にかなった複雑な動作をする機械を指し、たとえば自動販売機・ロボット・電卓などを含みます。
転じて、入力(情報)出力(応答・動作)の間に明確な関数関係があり、入力に対する認識と判断の機構と適切な出力を自動的にもつ数学的モデルを意味します。

有限オートマトンには

アクセプタ/リコグナイザ
トランスデューサ

の2種類があります。
前者では入力を受容・理解し、外界に結果を知らせるために状態を用いるのに対し、後者では与えられた入力と動作を伴う状態に基づいて出力を生成します。

有限オートマトンはノード(節)とエッジ(矢印)からなる状態遷移図を用いて図示されます。
ノードは状態、エッジは遷移をそれぞれ表します。
有限個の入力記号が定められ、現在の内部状態と入力記号によって、次の瞬間における出力と内部状態が決定されます。
すべての入力を読み終えたときに受理状態にあればその入力を受理し、 受理状態ではなければ入力を拒否します。

別の区分では、ひとつの入力記号について遷移先が一意に決定する決定性有限オートマトン (DFA)と、ひとつの入力記号について遷移先が複数存在する非決定性有限オートマトン (NFA) に分けられます。
全ての非決定性有限オートマトンは等価な決定性有限オートマトンに変換可能です。


有限オートマトンはその性質から文字列を認識することができ、一つの有限オートマトンが与えられると受理される文字列の一つの集合が定まります。
受理される文字列の集合を正規集合、文字列の集合を一つの文字列で表現する方法を正規表現とそれぞれ呼びます。
正規表現を用いると複雑な文字列検索が効率的になります。正規文法から生成され、正規表現で記述でき、有限オートマトンで受理できる言語を正規言語と呼びます。

有限オートマトンに特別の記憶装置(スタック)をつけたものをプッシュダウン・オートマトンといいます。
プッシュダウン・オートマトンは再帰的な構造を記述でき、正規表現よりも強力な表現力を持つ正規言語(文脈自由言語)を認識できます。

有限オートマトンはデジタル回路・プログラム・半導体・通信プロトコルの設計など工学面のほか、神経系や自然言語の文法のモデル化などに応用されています。

企業向けAI人材育成サービス

企業向けAI人材育成サービス

AI事業発足やAI導入に必要な人材育成のステップとAI研究所が提供するサービス。AI研究所の人材育成サービスでは、3つのステップを軸に御社の業務内でAIを活用できる人材育成やAIプロジェクトの支援を行います。

CTR IMG