Warning: Undefined variable $type in /home/users/1/sub.jp-asate/web/wiki/extensions/HeadScript/HeadScript.php on line 3
Warning: "continue" targeting switch is equivalent to "break". Did you mean to use "continue 2"? in /home/users/1/sub.jp-asate/web/wiki/includes/json/FormatJson.php on line 297
Warning: Trying to access array offset on value of type bool in /home/users/1/sub.jp-asate/web/wiki/includes/Setup.php on line 660
Warning: session_name(): Session name cannot be changed after headers have already been sent in /home/users/1/sub.jp-asate/web/wiki/includes/Setup.php on line 834
Warning: ini_set(): Session ini settings cannot be changed after headers have already been sent in /home/users/1/sub.jp-asate/web/wiki/includes/session/PHPSessionHandler.php on line 126
Warning: ini_set(): Session ini settings cannot be changed after headers have already been sent in /home/users/1/sub.jp-asate/web/wiki/includes/session/PHPSessionHandler.php on line 127
Warning: session_cache_limiter(): Session cache limiter cannot be changed after headers have already been sent in /home/users/1/sub.jp-asate/web/wiki/includes/session/PHPSessionHandler.php on line 133
Warning: session_set_save_handler(): Session save handler cannot be changed after headers have already been sent in /home/users/1/sub.jp-asate/web/wiki/includes/session/PHPSessionHandler.php on line 140
Warning: "continue" targeting switch is equivalent to "break". Did you mean to use "continue 2"? in /home/users/1/sub.jp-asate/web/wiki/languages/LanguageConverter.php on line 773
Warning: Cannot modify header information - headers already sent by (output started at /home/users/1/sub.jp-asate/web/wiki/extensions/HeadScript/HeadScript.php:3) in /home/users/1/sub.jp-asate/web/wiki/includes/Feed.php on line 294
Warning: Cannot modify header information - headers already sent by (output started at /home/users/1/sub.jp-asate/web/wiki/extensions/HeadScript/HeadScript.php:3) in /home/users/1/sub.jp-asate/web/wiki/includes/Feed.php on line 300
Warning: Cannot modify header information - headers already sent by (output started at /home/users/1/sub.jp-asate/web/wiki/extensions/HeadScript/HeadScript.php:3) in /home/users/1/sub.jp-asate/web/wiki/includes/WebResponse.php on line 46
Warning: Cannot modify header information - headers already sent by (output started at /home/users/1/sub.jp-asate/web/wiki/extensions/HeadScript/HeadScript.php:3) in /home/users/1/sub.jp-asate/web/wiki/includes/WebResponse.php on line 46
Warning: Cannot modify header information - headers already sent by (output started at /home/users/1/sub.jp-asate/web/wiki/extensions/HeadScript/HeadScript.php:3) in /home/users/1/sub.jp-asate/web/wiki/includes/WebResponse.php on line 46 https:///mymemo.xyz/wiki/api.php?action=feedcontributions&user=126.253.195.36&feedformat=atomminiwiki - 利用者の投稿記録 [ja]2024-05-09T13:32:07Z利用者の投稿記録MediaWiki 1.31.0オートマトン2017-07-01T15:32:54Z<p>126.253.195.36: </p>
<hr />
<div>{{otheruses|アルゴリズム|機械人形|オートマタ}}<br />
'''オートマトン''' (単数形: {{lang-en-short|automaton}} {{IPA-en|ɔːˈtɑməˌtɑn|}}, 複数形: [[オートマタ]]（{{lang|en|automata}} {{IPA-en|ɔːˈtɑmətə|}}）) とは、自動人形などとも呼ばれる「[[オートマタ]]」と同じ語であるが、[[計算理論]]において、[[計算モデル]]に関して[[有限オートマトン]]などの総称として使われる。また特に「オートマトン理論」と呼ばれる分野では、計算機械のうち[[計算可能関数|計算可能]]性の点で[[チューリングマシン]]よりも制限されているものを特に指して言うこともある。<br />
<br />
==種類==<br />
*[[有限オートマトン]]<br />
**[[決定性有限オートマトン|決定的有限オートマトン]] (Deterministic Finite Automata (DFA))<br />
**[[非決定性有限オートマトン|非決定的有限オートマトン]] (Nondeterministic Finite Automata (NFA))<br />
**[[非決定性有限オートマトン|ε動作を含む非決定的有限オートマトン]] (Nondeterministic Finite Automata, with ε transitions (FND-ε,ε-NFA))<br />
*[[プッシュダウン・オートマトン]] (Pushdown Automata (PDA))<br />
*[[線形拘束オートマトン]] (Linear Bounded Automaton (LBA))<br />
*[[生け垣オートマトン]](Hedge Automata)<br />
（広義のオートマトン）<br />
*[[チューリングマシン]] (Turing Machine)<br />
**決定的チューリングマシン(Deterministic Tuning Machine (DTM))<br />
**[[非決定性チューリングマシン|非決定的チューリングマシン]](Nondeterministic Tuning Machine (NTM))<br />
<br />
== 形式言語の階層とオートマトン ==<br />
{{main|形式言語の階層}}<br />
{{seealso|チョムスキー階層}}<br />
何らかの言語（特に[[形式言語]]）の文法（[[形式文法]]）と、それを生成する生成規則と、それを受理するオートマトンの間には対応関係があり、また言語を（形式言語を）集合とした場合に部分集合になっているという関係が階層をなしている、という事実がある。詳細は[[形式言語の階層]]の記事および[[チョムスキー階層]]の記事を参照。<br />
<br />
== 参考文献 ==<br />
*『オートマトン・言語理論の基礎』 米田政明 他 近代科学社 2003年 ISBN 4764902974<br />
*『Switching and Finite Automata Theory』 Zvi Kohavi, Niraj K. Jha Cambridge University Press 2009年 ISBN 0521857481<br />
<br />
==関連項目==<br />
* [[抽象機械]]<br />
* [[セル・オートマトン]]<br />
* [[状態機械]]<br />
* [[正規表現]]<br />
* [[形式文法]]<br />
<br />
{{DEFAULTSORT:おとまとん}}<br />
{{Computer-stub}}<br />
<br />
[[Category:計算理論]]<br />
[[Category:計算モデル]]<br />
[[Category:形式言語]]<br />
[[Category:数学に関する記事]]</div>126.253.195.36 Warning: Cannot modify header information - headers already sent by (output started at /home/users/1/sub.jp-asate/web/wiki/extensions/HeadScript/HeadScript.php:3) in /home/users/1/sub.jp-asate/web/wiki/includes/WebResponse.php on line 46