はじめに
neruneruna7，あるいは ねる7 です．
学びの足跡．
今回は余分な前書きは書きません．
本文
非決定性有限オートマトンと決定性有限オートマトンにおいて，言語の識別能力は同一である．
$L(dfa) = L(nfa) = L(\epsilon-nfa)$
$L$は言語
非決定性有限オートマトンは決定性有限オートマトンに変換可能である．
変換するアルゴリズムは2つあるが，そのうちの1つについて考える
変換方法
以下の空動作を持つ非決定性有限オートマトンM1について考える
JFLAPの都合，$\epsilon$ではなく$\lambda$になっているが，気にせぬよう．
\begin{align}
M_{1} &= <Q,\Sigma,\delta,q_{0},F> \\
Q&= \{q_{0}, q_{1}, q_{2}\} \\
\Sigma &= \{0,1\} \\
\delta&: Q \times (\Sigma \cup \{\epsilon\}) = 2^{Q}
\\
&\delta(q_{0},0)=\{q_{0}\},\delta(q_{0}, \epsilon)=\{q_{1}\} \\
&\delta(q_{1},0)=\{q_{2}\},\delta(q_{1},1)=\{q_{1}\}\\
&\delta(q_{2},0)=\{q_{2}\},\delta(q_{2},1)=\{q_{0}\}
\\
q_{0}&=q_{0} \\
F&=q_{2}
\end{align}
受理する語は，10，000001000,0100110,などがある．
この非決定性有限オートマトンオートマトンをもとに，決定性有限オートマトン$Md$を構成する
-
初期状態からの空動作があれば，それらをまとめて$Md$の初期状態とする．
$\delta(q_{0},\epsilon)={q_{1}}$より，${q_{0},q_{1}}$を$Md$の初期状態とする． -
つくった初期状態には$q_{0}$と$q_{1}$という2つの状態が含まれている．これらの状態から，遷移できる先の和集合及び空動作で遷移できる状態の集合を新たな状態として作る.ここで作った状態に対しても，それを行い，新たな状態を作れなくなるまで繰り返す．
\begin{aligned}
\delta(q_{0},0) \cup \delta(q_{1},0) = \{q_{0},q_{2}\} \\
\{q_{0},q_{2}\}のうち，q_{0}からは空動作でq_{1}へ移動できるため，それを加えて \\
\delta(\{q_{0},q_{1}\},0)=\{q_{0},q_{1},q_{2}\}
\\
\\
\delta(q_{0},1) \cup \delta(q_{1},1) = \{q_{1}\} \\
\{q_{1}\}からの空動作はない \\
\delta(\{q_{0},q_{1}\},1)=\{q_{1}\}
\\
\\
\\
\delta(q_{0},0) \cup \delta(q_{1},0) \cup \delta(q_{2},0) = \{q_{0},q_{2}\} \\
\{q_{0},q_{2}\}のうち，q_{0}からは空動作でq_{1}へ移動できるため，それを加えて \\
\delta(\{q_{0},q_{1},q_{2}\},0)=\{q_{0},q_{1},q_{2}\}
\\
\\
\delta(q_{0},1) \cup \delta(q_{1},1) \cup \delta(q_{2},1) = \{q_{0},q_{1}\} \\
\{q_{0},q_{1}\}のうち，q_{0}からは空動作でq_{1}へ移動できるため，それを加えて \\
\delta(\{q_{0},q_{1},q_{2}\},1)=\{q_{0},q_{1}\}
\\
\\
\\
\delta(\{q_{1}\},0) = \{q_{2}\} \\
\{q_{2}\}からの空動作はない \\
\delta(\{q_{1}\},0) = \{q_{2}\} \\
\\
\delta(\{q_{1}\},1) = \{q_{1}\} \\
\{q_{1}\}からの空動作はない \\
\delta(\{q_{1}\},1) = \{q_{1}\} \\
\\
\\
\\
\delta(\{q_{2}\},0) = \{q_{2}\} \\
\{q_{2}\}からの空動作はない \\
\delta(\{q_{2}\},0) = \{q_{2}\} \\
\\
\delta(\{q_{2}\},1) = \{q_{0}\} \\
q_{0}からは空動作でq_{1}へ移動できるため，それを加えて \\
\delta(\{q_{2}\},1) = \{q_{0},q_{1}\} \\
\\
これ以上新たな状態は作れない
\end{aligned}
- M1の受理状態を1つでも含む状態を，Mdでの受理状態とする
$F={{q_{2}}, {q_{0},q_{1},q_{2}}}$
決定性有限オートマトンを構成できた．
感想
有限オートマトンはシンプルでわかりやすいオートマトンである．しかし，非決定性となると，動作を人力で追うのは辛かった（学ぶ上でどうしても自力で追って理解する過程を通らなければならない）．非決定性から決定性への変換も，理解するまではなんじゃこりゃと思った．
何かを有限オートマトンに落とし込むときは非決定性の方が楽だろうし，有限オートマトンをプログラムするときは決定性の方が楽なんだろうなと感じた．その間の変換が機械的にできるというのは，理解してしまえばとても便利なものだなと思う．
参考
- オートマトン・言語理論の基礎 著者：米田政明 広瀬貞樹 大里延康 大川知 出版：近代科学社
- 大学の講義