オートマトン

出典: フリー百科事典『ウィキペディア（Wikipedia）』
（オートマトン理論から転送）
曖昧さ回避 この項目では、計算のアルゴリズムについて説明しています。
曖昧さ回避 「オートメーション」とは異なります。
オートマトン理論

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

種類[編集]

広義のオートマトン

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

詳細は「形式言語の階層」を参照
「チョムスキー階層」も参照

何らかの言語（特に形式言語）の文法（形式文法）と、それを生成する生成規則と、それを受理するオートマトンの間には対応関係があり、また言語を（形式言語を）集合とした場合に部分集合になっているという関係が階層をなしている、という事実がある。詳細は形式言語の階層の記事およびチョムスキー階層の記事を参照。

参考文献[編集]

  • 米田政明 他 『オートマトン・言語理論の基礎』、 近代科学社、2003年、ISBN 4-7649-0297-4
  • 岩間 一雄：「オートマトン・言語と計算理論」、コロナ社、ISBN 978-4339018219（2003年10月）。
  • Zvi Kohavi; Niraj K. Jha (2009), Switching and Finite Automata Theory (3rd ed.), Cambridge University Press, ISBN 0521857481, ISBN 9780521857482 

関連項目[編集]

スタブアイコン

この項目は、コンピュータに関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（PJ:コンピュータ/P:コンピュータ）。

「https://ja.wikipedia.org/w/index.php?title=オートマトン&oldid=99859520」から取得