オートマトン

英

automaton

関

自動機械

WordNet

1. a mechanism that can move automatically (同)robot, golem
2. someone who acts or responds in a mechanical or apathetic way; "only an automaton wouldnt have noticed" (同)zombi, zombie

PrepTutorEJDIC

1. 自動機械,自動装置 / 人造人間,ロボット / 機械的に行動する人(動物)

Wikipedia preview

出典(authority):フリー百科事典『ウィキペディア（Wikipedia）』「2017/01/16 14:46:23」(JST)

wiki ja

[Wiki ja表示]

オートマトン (英: automaton [ɔːˈtɑməˌtɑn], 複数形 automata [ɔːˈ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))
• チューリングマシン (Turing Machine)
  • 決定性チューリングマシン(Deterministic Tuning Machine (DTM))
  • 非決定性チューリングマシン(Nondeterministic Tuning Machine (NTM))
• 生け垣オートマトン(Hedge Automata)

言語のクラス関係

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

形式言語との関係

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

• 有限オートマトン ― 正規文法 ― 正規表現: 正規言語を記述できる
• プッシュダウン・オートマトン ― 文脈自由文法: 文脈自由言語を記述できる
• 線形拘束オートマトン ― 文脈依存文法: 文脈依存言語を記述できる
• チューリングマシン ― 句構造文法: 句構造言語を記述できる

チューリングマシン

「チューリングマシン」を参照

参考文献

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

関連項目

• 抽象機械
• セル・オートマトン
• 状態機械
• 正規表現
• 形式文法

UpToDate Contents

全文を閲覧するには購読必要です。 To read the full text you will need to subscribe.

• 1. Depersonalization/derealization disorder: Epidemiology, pathogenesis, clinical manifestations, course, and diagnosis
• 2. Treatment of depersonalization/derealization disorder

Japanese Journal

• 車間制御機能を考慮した交通流のモデル化と解析

• 星野 貴弘,吉田 吏志,浜松 芳夫
• 電気学会論文誌. D, 産業応用部門誌 = IEEJ transactions on industry applications 135(7), 765-774, 2015-07
• NAID 40020534702

• 車長を考慮した交通流セルオートマトンモデルの提案と解析 (ITS研究会 交通管理,情報提供システム,ITS一般)

• 奈良橋 諭,星野 貴弘,浜松 芳夫
• 電気学会研究会資料. ITS 2015(15-22), 15-18, 2015-06-19
• NAID 40020522417

• 内部状態数の少ないセルオートマトンで生成される数列についての考察 (複雑コミュニケーションサイエンス)

• 上川 直紀,梅尾 博司
• 電子情報通信学会技術研究報告 = IEICE technical report : 信学技報 115(78), 103-108, 2015-06-11
• NAID 40020525308

Related Pictures

---

★リンクテーブル★

リンク元	「automaton」「自動機械」
関連記事	「トマト」

「automaton」

　　[★]

オートマトン、自動機械 　 　 　

「自動機械」

　　[★]

英

automaton

関

オートマトン

「トマト」

　　[★]

英

tomato、Lycopersicon esculentum、Solanum lycopersicum

関

アカナス