決定性有限オートマトンと状態遷移図

ショートカット: 違い、類似点、ジャカード類似性係数、参考文献。

決定性有限オートマトンと状態遷移図の違い

決定性有限オートマトン vs. 状態遷移図

決定性有限オートマトン（けっていせいゆうげんオートマトン、Deterministic Finite Automaton）または決定性有限状態機械（けっていせいゆうげんじょうたいきかい、Deterministic Finite State Machine）は、状態と入力によって次に遷移すべき状態が一意に定まる有限オートマトンである。DFA と略記される。 DFAは入力文字列を受け付ける。各入力文字について、遷移関数にしたがって新たな状態に遷移する。最後に入力文字を受け付けたとき、受理状態であれば入力文字列は受理された、そうでなければ入力文字列は拒否されたと判断される。 非決定性有限オートマトンは、決定性有限オートマトンと同じように正規集合を認識でき、必ず決定性オートマトンに変換できる。. 態遷移図（じょうたいせんいず、State Transition Diagram）は、有限オートマトンなどの状態機械について、その各状態を頂点とし、状態から状態への各遷移を辺としたグラフ構造に注目して、グラフィカルに表現した図である。他の表現手法として状態遷移表などがある。 状態遷移図にはいくつかの異なる形式のものがある。対象の性質や用途などによって使い分けることもある。.

状態遷移表

態遷移表（じょうたいせんいひょう、State Transition Table）は、状態機械類（の遷移関数 T(scurrent, e).

決定性有限オートマトンと状態遷移表 · 状態遷移図と状態遷移表 · 続きを見る »

非決定性有限オートマトン

非決定性有限オートマトン（）または非決定性有限状態機械（）は、有限オートマトンの一種であり、ある状態と入力があったとき、次の遷移先が一意に決定しないことがあるものである。NFAと略記される。.

決定性有限オートマトンと非決定性有限オートマトン · 状態遷移図と非決定性有限オートマトン · 続きを見る »

有限オートマトン

有限オートマトン（finite automaton)または有限状態機械（finite state machine, FSM）とは、有限個の状態と遷移と動作の組み合わせからなる数学的に抽象化された「ふるまいのモデル」である。デジタル回路やプログラムの設計で使われることがあり、ある一連の状態をとったときどのように論理が流れるかを調べることができる。有限個の「状態」のうち1つの状態をとる。ある時点では1つの状態しかとらず、それをその時点の「現在状態」と呼ぶ。何らかのイベントや条件によってある状態から別の状態へと移行し、それを「遷移」と呼ぶ。それぞれの現在状態から遷移しうる状態と、遷移のきっかけとなる条件を列挙することで定義される。 有限オートマトンは様々な問題に応用でき、半導体設計の自動化、通信プロトコル設計、構文解析などの工学面での応用がある。生物学や人工知能研究では状態機械（群）を使って神経系をモデル化し、言語学では自然言語の文法をモデル化したりする。.

有限オートマトンと決定性有限オートマトン · 有限オートマトンと状態遷移図 · 続きを見る »