この記事での学習内容 基本情報 応用情報
有限オートマトンの概念、形式言語との関係、チューリング機械との関係、状態遷移表、状態遷移図を理解する。
用語例：プッシュダウンオートマトン
オートマトン
プログラミング言語などの形式言語で記述された分を解釈するための仮想的な機械概念をオートマトンといいます。
コンピュータそのものを数学的な観点からモデル化し、アルゴリズム（＝問題解決のための処理手順）を定型化したものです。
元々は「自動人形」を意味している言葉で、現代のコンピュータ技術の基礎原理の一つとして、様々な場面で応用されています。
オートマトンのモデルでは、コンピュータを外部からの入力に応じて内部の状態が変化し外部に出力を行うものとして扱います。
なお、オートマトンとコラム「コンピュータの歴史」で紹介した「チューリング機械」というのは非常に似たものとなっていて、オートマトンの定義を拡張したものがチューリング機械となっています。
チューリング機械は無限の記憶領域を持つとされているが、0と1という記号の並びを入力として、順次処理を行い、後戻りしない、という共通点があります。
有限オートマトン
オートマトンの中で有限個の状態を扱うものを、特に「有限オートマトン」と呼びます。有限オートマトンでは、開始時点の状態（＝初期状態）が決まっています。そして、入力によって他の状態へ変化（＝遷移）します。最後に成功して終了する状態（＝受容状態）のどれかに遷移すれば終了とします。
以下に有限オートマトンの特徴をまとめました。
- 一つの初期状態を取る。
- 有限な記憶領域を持つ。
- 記号列を入力とし、一度に１つずつ読み込む。
- 後戻りしない。
- 入力に応じて、他の状態の遷移する。
- 特定の状態のどれかで終わっていれば成功。受容状態となる。
例えば、「ノートパソコンの電源投入状態」を有限オートマトンで考えてみましょう。
このノートパソコンは、閉じると休止状態となり、開くと休止状態から復帰するものとします。
- 初期状態は、電源が入っていない「停止」状態です。
- 「電源スイッチON」という入力によって、状態は「動作」に遷移します。
- 「動作」状態でパソコンを閉じると「休止」に遷移します。
- 「休止」状態でパソコンを開くと「動作」に遷移します。
- 「シャットダウン」という入力によって、「停止」に遷移し、終了します。
他に身近な例では、有限オートマトンの考え方で表現できるものとしては、「自動販売機」があります。
状態遷移表と状態遷移図
オートマトンの状態を表すものには、「状態遷移表」と「状態遷移図」があります。
どの状態の時に、どの入力があると、どの状態に変化（遷移）するのかを示す規則を、表にしたものが状態遷移表、図にしたものが状態遷移図です。
先述のノートパソコンの例を元に、状態遷移表と状態遷移図を確認してみましょう。
まずは、状態遷移表を示します。
縦が遷移前の状態、横が入力、表の中は遷移後の状態を表しています。なお、標柱の横棒は遷移がないことを示します。
次に状態遷移図を見てみましょう。
状態を楕円形で、入力を矢印によって、状態の遷移を視覚的に分かりやすいように表現しています。
プッシュダウンオートマトン
有限オートマトンの「状態」と「入力」に加えて、無限の容量の「スタック」を持っているのが、プッシュダウンオートマトンと呼ばれるものです。
スタックを持つことに加え、以下の点で有限オートマトンとは異なっています。
- スタックのトップ（＝最上位の要素）でなすべき状態遷移を判断する。
- 遷移実行の一部として、スタック操作を行うことが出来る。