有限オートマトンの種類

非決定性有限オートマトン Nondeterministic Finite Automaton[NFA]	状態 $Q$ と入力 $\Sigma$ の組 $(Q,\Sigma)$ に対して，複数の状態遷移があるような有限オートマトン．
決定性有限オートマトン Deterministic Finite Automaton[DFA]	状態 $Q$ と入力 $\Sigma$ の組 $(Q,\Sigma)$ に対して，1つの状態遷移しかない有限オートマトン

非決定性有限オートマトン Nondeterministic Finite Automaton[NFA]

\[\begin{xy}\xymatrix{&*++[o][F-]{q_{0}} \ar@(ur,ul)_1 \ar[d]^{b,a} \ar[r]^{a,b} & *++[o][F=]{q_{1}}\ar@(ru,rd) []^{a,b} \\&*++[o][F=]{q_{2}}\ar@(ru,rd) []^{b,a}& }\end{xy}\]上の非決定性有限オートマトン[NFA]では，\[\{ab,aa,aab,aba,abb,\cdots\}\]といった文字列を受理します．

決定性有限オートマトン Deterministic Finite Automaton[DFA]

\[\begin{xy}\xymatrix{&*++[o][F-]{q_{0}} \ar@(ur,ul)_1 \ar[d]^{b} \ar[r]^{a} & *++[o][F=]{q_{1}}\ar@(ru,rd) []^{a} \\&*++[o][F=]{q_{2}}\ar@(ru,rd) []^{b}& }\end{xy}\]上の決定性有限オートマトン[DFA]では，\[\{aa,aa,aaa,\cdots\}\]といった文字列を受理します．

Mathematics is the language with which God has written the universe.