有限オートマトンの種類
非決定性有限オートマトン
Nondeterministic Finite Automaton[NFA] | 状態 $Q$ と入力 $\Sigma$ の組 $(Q,\Sigma)$ に対して，複数の状態遷移があるような有限オートマトン． |
決定性有限オートマトン
Deterministic Finite Automaton[DFA] | 状態 $Q$ と入力 $\Sigma$ の組 $(Q,\Sigma)$ に対して，1つの状態遷移しかない有限オートマトン |
\[\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\}\]といった文字列を受理します．
\[\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.
