コンピュータ

有限オートマトンとは

オートマトン

オートマトン(英:automaton)とは、自動人形という意味を持つ言葉であり、コンピュータの状態、遷移をモデル化したものです。

例えば、自動販売機は「お金を入れる」(入力)→「ボタンが点灯」(状態の遷移)、「点灯したボタンを押す」(入力)→「ジュースが出てくる」(状態の遷移)のような動作をします。

このように状態の遷移にともなう動作をモデル化してあらわすのがオートマトンです。

オートマトンにはいくつかの種類があり、その中でも代表的なモデルが「有限オートマトン」です。

基本情報技術者試験や応用情報技術者試験でもよく出題される言葉です。
なんか難しそうだ・・・

スポンサーリンク

有限オートマトン

有限オートマトン(英:finite automaton)とは、状態や遷移の数が有限個であらわされるオートマトンのことです。

有限オートマトンは次のような「状態遷移表」と「状態遷移図」を用いて表現します。

■状態遷移表の例

状態遷移表

■状態遷移図の例

状態遷移図

状態遷移図は、次の記号で表現します。

名称記号説明
状態状態状態をあらわす
受理状態受理状態受理状態をあらわす
遷移遷移遷移をあらわす

有限オートマトンには「受理」と「非受理」があり、入力終了時に受理状態であれば受け付けを完了し、受理状態でないものは非受理となり受け付けません。

有限オートマトンの実行例

それでは、もう少し具体的に有限オートマトンの流れを見ていきましょう。

例えば、次のような状態遷移表があるとします。

状態遷移表の例

この状態遷移表から、状態遷移図を作ると次のような図が作成できます。この状態遷移図は入力データが「すべて数値なら受理」、「数値以外があれば非受理」という有限オートマトンです。※状態Aを初期状態(開始地点)としています。

状態遷移図の例

受理の例(入力データ「12」)

この状態遷移図に入力データ「12」を与えたときの流れは次の通りです。

【手順1】「1」で「状態C」に遷移

初期状態は「状態A」なので「状態A」を開始地点とします。はじめの入力データ「1」は数値なので「状態A」→「状態C」に遷移します。

【手順1】「1」でCに遷移

[手順2]「2」で「状態C」のままとなり"受理"

続いての入力データ「2」は数値なので「状態C」のままです。これで入力は終了です。

入力終了時の状態が「受理状態」なので、入力「12」は受理します。

【手順2】「2」でCのままで受理

非受理の例(入力データ「1a」)

この状態遷移図に入力データ「1a」を与えたときの流れは次の通りです。

【手順1】「1」で「状態C」に遷移

初期状態は「状態A」なので「状態A」を開始地点とします。はじめの入力データ「1」は数値なので「状態A」→「状態C」に遷移します。

【手順1】「1」でCに遷移

[手順2]「a」で「状態B」となり"非受理"

続いての入力データ「a」は数値ではないので「状態C」→「状態B」に遷移します。これで入力は終了です。

入力終了時の状態が「受理状態」ではないので、入力「1a」は非受理となり、受理しません。

【手順2】「a」でBとなり非受理

helpful