前のページ 1/1 次のページ

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

・外から、連続している情報が入力される

・内部に「状態」を保持する

・外へ、何らかの情報を出力する

携帯電話を例にとると、キーを押すことによってさまざまな機能が使用できるが、その機能はキーと必ずしも1対1で連動しているわけではない。「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)

・生け垣オートマトン(Hedge Automata)

◆形式言語との関係

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

・有限オートマトン ― 正規文法 ― 正規表現: 正規言語を記述できる

・プッシュダウン・オートマトン ― 文脈自由文法: 文脈自由言語を記述できる

・線形拘束オートマトン ― 文脈依存文法: 文脈依存言語を記述できる

・チューリングマシン ― 句構造文法: 句構造言語を記述できる

◆チューリングマシン

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

◆ 参考文献

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

◆関連項目

・ セル・オートマトン

・ 状態機械

・ 正規表現

・ 形式文法

前のページ 1/1 次のページ

・オートマトン page1