オートマトン

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

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

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

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

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

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

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

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

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

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

参考文献[編集]

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

関連項目[編集]