Wikipedia

「オートマトン」の版間の差分

履歴の双方向閲覧
← 古い編集新しい編集 →
削除された内容 追加された内容
ビジュアルウィキテキスト
m編集の要約なし
編集の要約なし
1行目:
{{otheruses|アルゴリズム|機械人形|オートマタ}}
'''オートマトン''' (単数形: {{lang-en-short|automaton}} {{IPA-en|ɔːˈtɑməˌtɑn|}}, 複数形: [[オートマタ]]（{{lang|en|automata}} {{IPA-en|ɔːˈtɑmətə|}}）) とは、自動人形などとも呼ばれる「[[オートマタ|自動人形]]」を意味している言葉と同じ語であるが、情報科学の分野[[計算理論]]において、[[計算モデル]]に関して[[有限オートマトン]]などの総称として使われる。また特に「オートマトン理論」と呼ばれる分野では、次計算機械のような特徴を持ったち[[計算可能関数|計算可能]]性の点で[[チューリングマシステムン]]よりも制限されているものを特に指して言うことでもある。
 
==種類==
*外から、連続している情報が入力される
*内部に「状態」を保持する
*外へ、何らかの情報を出力する
 
[[携帯電話]]を例にとると、キーを押すことによってさまざまな機能が使用できるが、その機能はキーと必ずしも1対1で連動しているわけではない。例えば電話番号の入力中に「5」のキーを押すと画面に5が現れるが、日本語の入力中に「5」のキーを押すと「な」が現れる。他にも、画面上のキャラクターが行動したり、決定キーの代わりとして動作する場合もあるなど様々である。これは今までに入力された情報によって内部の状態が変化しているからである。このように入力がなされた時点での「文脈」に対して複雑な解釈を行うような仕組みをオートマトンという。
 
==オートマトンの種類==▼
*[[有限オートマトン]]
**[[決定性有限オートマトン|決定的有限オートマトン]] (Deterministic Finite Automata (DFA))
**[[非決定性有限オートマトン|非決定的有限オートマトン]] (Nondeterministic Finite Automata (NFA))
**[[非決定性有限オートマトン|ε動作を含む非決定性的有限オートマトン]] (Nondeterministic Finite Automata, with ε transitions (FND-ε,ε-NFA))
*[[プッシュダウン・オートマトン]] (Pushdown Automata (PDA))
*[[線形拘束オートマトン]] (Linear Bounded Automaton (LBA))
*[[生け垣オートマトン]](Hedge Automata)▼
▲==（広義のオートマトンの種類==）
*[[チューリングマシン]] (Turing Machine)
**[[決定性的チューリングマシン]](Deterministic Tuning Machine (DTM))
**[[非決定性チューリングマシン|非決定的チューリングマシン]](Nondeterministic Tuning Machine (NTM))
▲*[[生け垣オートマトン]](Hedge Automata)
 
== 言語のクラス関係 ==
[[チョムスキー階層]]に基づいたオートマトンが受理する言語のクラス間の関係を次のように表せる。<br />
L(DTM) = L(NTM)⊃L(LBA)⊃L(PDA)⊃L(DFA) = L(NFA) = L(ε-NFA)
 
==形式言語との関係==▼
{{節stub}}
オートマトンが[[受理]]する[[形式言語|言語]]と[[形式文法]]によって[[導出]]される言語には対応関係がある。
 
*[[有限オートマトン]] ― [[正規文法]] ― [[正規表現]]: [[正規言語]]を記述できる
*[[プッシュダウン・オートマトン]] ― [[文脈自由文法]]: [[文脈自由言語]]を記述できる
*[[線形拘束オートマトン]] ― [[文脈依存文法]]: [[文脈依存言語]]を記述できる
*[[チューリングマシン]] ― [[句構造文法]]: [[句構造言語]]を記述できる
 
==チュ 形式言語の階層とオーリングトマシトン ==
▲=={{main|形式言語との関係==階層}}
{{see|[[チューリングマシン]]}}
{{seealso|チョムスキー階層}}
何らかの言語（特に[[形式言語]]）の文法（[[形式文法]]）と、それを生成する生成規則と、それを受理するオートマトンの間には対応関係があり、また言語を（形式言語を）集合とした場合に部分集合になっているという関係が階層をなしている、という事実がある。詳細は[[形式言語の階層]]の記事および[[チョムスキー階層]]の記事を参照。
 
== 参考文献 ==
「https://ja.wikipedia.org/wiki/オートマトン」から取得