有限オートマトンの種類

非決定性有限オートマトン
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\}\]といった文字列を受理します.

Vita brevis, ars longa. Omnia vincit Amor.





















C*環 剰余の定理(Remainder theorem) 商と余り 合同 剰余類(residue class)