実数を表す文字列を受理するオートマトン②

自分の理解力の無さから、参考にしようとしていたサイトの説明では行き詰ってしまった。なのでオートマトンの教科書を読んでみた。
ε動作ありのNFAから、ε動作なしのNFAへの変換のやり方が書いてあったので、やってみた。
まず\epsilon-Cl(S_{i})(ε閉包というらしい)というものを定義してみる。これは状態S_{i}からε動作だけで到達できる状態の集合(ただしS_{i}自身の含む)を表す。

状態S_{i} \epsilon-Cl(S_{i})
S_{0} \left\{S_{0},S_{1}\right\}
S_{1} \left\{S_{1}\right\}
S_{2} \left\{S_{2},S_{3},S_{5},S_{13},S_{19}\right\}
S_{3} \left\{S_{3}\right\}
S_{4} \left\{S_{3},S_{4},S_{5},S_{13},S_{19}\right\}
S_{5} \left\{S_{5},S_{13},S_{19}\right\}
S_{6} \left\{S_{6},S_{7},S_{13},S_{19}\right\}
S_{7} \left\{S_{7}\right\}
S_{8} \left\{S_{7},S_{8},S_{13},S_{19}\right\}
S_{9} \left\{S_{9}\right\}
S_{10} \left\{S_{10},S_{11},S_{13},S_{19}\right\}
S_{11} \left\{S_{11}\right\}
S_{12} \left\{S_{11},S_{12},S_{13},S_{19}\right\}
S_{13} \left\{S_{13},S_{19}\right\}
S_{14} \left\{S_{14},S_{15}\right\}
S_{15} \left\{S_{15}\right\}
S_{16} \left\{S_{16},S_{17},S_{19}\right\}
S_{17} \left\{S_{17}\right\}
S_{18} \left\{S_{17},S_{18},S_{19}\right\}
S_{19} \left\{S_{19}\right\}

状態集合Xに対して、\epsilon-Cl(X)=\bigcup_{p\in X}\epsilon-Cl(p)を定義する。これを踏まえて、元のオートマトンM=(Q,\Sigma,\delta,S_{0},F)から新しいオートマトンM^{'}=(Q,\Sigma,\delta^{'},S_{0},F^{'})を作れば、それがε遷移を含まないNFAになっているのだと。

ε動作を許さないNFAの状態遷移

新しい状態遷移関数を\delta^{'}とすると、\delta^{'}(p,a)=\epsilon-Cl(\delta(\epsilon-Cl(p),a)) となる。
\delta^{'}の定義を元に、例として、状態S_{1}で入力Yの場合の遷移を求めると以下の通り。
\delta^{'}(S_{1},Y)=\epsilon-Cl(\delta(\epsilon-Cl(S_{1}),Y))=\epsilon-Cl(\delta(\{S_{1}\},Y))=\epsilon-Cl(\{S_{2}\})=\{S_{2},S_{3},S_{5},S_{13},S_{19}\}
新しい状態遷移関数\delta^{'}を元に状態遷移表つくってみた。

状態S_{i} X Y Z .
S_{0} \{S_{1}\} \{S_{2},S_{3},S_{5},S_{13},S_{19}\} \{S_{9}\}
S_{1} \{S_{2},S_{3},S_{5},S_{13},S_{19}\} \{S_{9}\}
S_{2} \{S_{3},S_{4},S_{5},S_{13},S_{19}\} \{S_{14},S_{15}\} \{S_{6},S_{7},S_{13},S_{19}\}
S_{3} \{S_{3},S_{4},S_{5},S_{13},S_{19}\}
S_{4} \{S_{3},S_{4},S_{5},S_{13},S_{19}\} \{S_{14},S_{15}\} \{S_{6},S_{7},S_{13},S_{19}\}
S_{5} \{S_{14},S_{15}\} \{S_{6},S_{7},S_{13},S_{19}\}
S_{6} \{S_{7},S_{8},S_{13},S_{19}\} \{S_{14},S_{15}\}
S_{7} \{S_{7},S_{8},S_{13},S_{19}\}
S_{8} \{S_{7},S_{8},S_{13},S_{19}\} \{S_{14},S_{15}\}
S_{9} \{S_{10},S_{11},S_{13},S_{19}\}
S_{10} \{S_{11},S_{12},S_{13},S_{19}\} \{S_{14},S_{15}\}
S_{11} \{S_{11},S_{12},S_{13},S_{19}\}
S_{12} \{S_{11},S_{12},S_{13},S_{19}\} \{S_{14},S_{15}\}
S_{13} \{S_{14},S_{15}\}
S_{14} \{S_{15}\} \{S_{16},S_{17},S_{19}\}
S_{15} \{S_{16},S_{17},S_{19}\}
S_{16} \{S_{17},S_{18},S_{19}\}
S_{17} \{S_{17},S_{18},S_{19}\}
S_{18} \{S_{17},S_{18},S_{19}\}
S_{19}

ε動作を許さないNFAの受理状態集合

新しい受理状態集合F^{'}は以下の通り。

  • \epsilon-Cl(S_{0}) \cap F \neq \emptysetのとき:F^{'} = F \cup \{ S_{0} \}
  • \epsilon-Cl(S_{0}) \cap F = \emptysetのとき:F^{'} = F

したがって、この例では、F=F^{'}=\{S_{19}\}