オートマトン

オートマトン (automaton (pl: automata)) とは「自動人形」を意味している言葉で、情報科学の分野においては、次のような特徴を持ったシステムのことである。

• 外から、連続している情報が入力される
• 内部に「状態」を保持する
• 外へ、何らかの情報を出力する

携帯電話を例にとると、キーを押すことによってさまざまな機能が使用できるが、その機能はキーと必ずしも1対1で連動しているわけではない。例えば電話番号の入力中に「5」のキーを押すと画面に5が現れるが、日本語の入力中に「5」のキーを押すと「な」が現れる。他にも、画面上のキャラクターが行動したり、決定キーの代わりとして動作する場合もあるなど様々である。これは今までに入力された情報によって内部の状態が変化しているからである。このように入力がなされた時点での「文脈」に対して複雑な解釈を行うような仕組みをオートマトンという。

オートマトンの種類

• 有限オートマトン
  • 決定性有限オートマトン (Deterministic Finite Automata (DFA))
  • 非決定性有限オートマトン (Nondeterministic Finite Automata (NFA))
  • ε動作を含む非決定性有限オートマトン (Nondeterministic Finite Automata, with ε transitions (FND-ε,ε-NFA))
• プッシュダウン・オートマトン (Pushdown Automata (PDA))
• 線形拘束オートマトン (Linear Bounded Automaton (LBA))
• チューリングマシン (Turing Machine)
  • 決定性チューリングマシン(Deterministic Tuning Machine (DTM))
  • 非決定性チューリングマシン(Nondeterministic Tuning Machine (NTM))
• 生け垣オートマトン(Hedge Automata)

言語のクラス関係

チョムスキー階層に基づく、オートマトンが受理する言語のクラス間の関係は次のように表される。</br> L(DTM)=L(NTM)⊃L(LBA)⊃L(PDA)⊃L(DFA)=L(NFA)=L(ε-NFA)

形式言語との関係

テンプレート:節stub オートマトンが受理する言語と形式文法によって導出される言語には対応関係がある。

• 有限オートマトン ― 正規文法 ― 正規表現: 正規言語を記述できる
• プッシュダウン・オートマトン ― 文脈自由文法: 文脈自由言語を記述できる
• 線形拘束オートマトン ― 文脈依存文法: 文脈依存言語を記述できる
• チューリングマシン ― 句構造文法: 句構造言語を記述できる

チューリングマシン

テンプレート:節stub チューリングマシンはオートマトンの定義を拡張して、入力・出力を同じ一本のテープから行い、代わりに双方向に移動できる（入力も出力も自分で思う順序で行える）ようにしたものである。

参考文献

• 『オートマトン・言語理論の基礎』　米田政明 他　　近代科学社

関連項目

• 抽象機械
• セル・オートマトン
• 状態機械
• 正規表現
• 形式文法

テンプレート:Asbox