オートマトン

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

オートマトン (単数形: : automaton [ɔːˈtɑməˌtɑn], 複数形: オートマタautomata [ɔːˈtɑmətə])) とは、自動人形などとも呼ばれる「オートマタ」と同じ語であるが、計算理論において、計算モデルに関して有限オートマトンなどの総称として使われる。また特に「オートマトン理論」と呼ばれる分野では、計算機械のうち計算可能性の点でチューリングマシンよりも制限されているものを特に指して言うこともある。

種類[編集]

(広義のオートマトン)

形式言語の階層とオートマトン[編集]

何らかの言語(特に形式言語)の文法(形式文法)と、それを生成する生成規則と、それを受理するオートマトンの間には対応関係があり、また言語を(形式言語を)集合とした場合に部分集合になっているという関係が階層をなしている、という事実がある。ただし、チューリングマシンが認識できない言語、すなわち帰納的加算でない言語も存在する。詳細は形式言語の階層の記事およびチョムスキー階層の記事を参照。

参考文献[編集]

  • 長尾真(1999)「数理言語学」長尾真・中川裕志・松本裕治・橋田浩一・John.B『岩波講座 言語の科学8 言語の数理』岩波書店 p.39 ISBN 4000108581
  • 『オートマトン・言語理論の基礎』 米田政明 他  近代科学社 2003年 ISBN 4764902974
  • 『Switching and Finite Automata Theory』 Zvi Kohavi, Niraj K. Jha Cambridge University Press 2009年 ISBN 0521857481

関連項目[編集]