オートマトン

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

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

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

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

オートマトンの種類[編集]

言語のクラス関係[編集]

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

形式言語との関係[編集]

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

チューリングマシン[編集]

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


参考文献[編集]

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

関連項目[編集]