ε-非決定性有限オートマトンについて

　先の記事で決定性有限オートマトンが認識する言語のクラス $\mathcal{L}_{\text{DFA}}$ と, 非決定性有限オートマトンが認識する言語のクラス $\mathcal{L}_{\text{NFA}}$ が一致することについて書きました. 結局, いまだにわたしが理解したいことごとは浮かんだままですが, 前へ進んで, 今回は $\epsilon$-非決定性有限オートマトンについて書こうと思います.
　わからないことがあるというより, 教科書では証明が省略されていたので, わたしが考えた証明にまちがっているところがないかみてもらいたいのです. ただ, 省略された理由が「明らかだから」だとすると, わたしがいろいろと考察した道は遠回りということにもなるかもしれません. なので, もっと単純に証明ができるならばぜひ教えてください. よろしくお願いします.

　先の記事では $\delta^{*}_{N}$ を $2^{Q} \times \Sigma^{*}$ から $2^{Q}$ への写像として定め, その理由を「帰納的な性質を持つから」と言いましたが, 実際にある語が受理されるかされないかの計算を行ってみると, $\delta^{*}_{N}(\{q_{0}\}, w)$ しか考えなくてよく, たとえば $\delta^{*}_{N}(\{ q_{1}, q_{2}\}, w)$ などは考えてもあまり意味はないと思ったので, 今回は始域を $\Sigma^{*}$ として, $\delta^{*}_{N}(\epsilon) = \{ q_{0} \}$ としました. これはちょっとした質問なのですが, このように定義することでなにか具合のわるいことが起きるでしょうか.

　実を言うと, よくわかっていません. 入力が与えられたときに状態が遷移することは自然なふうに思えます. 一方で「なにも入力されない」ことで「動かない」というのもひとつの遷移と考えられると思えば $\delta_{\epsilon}(q, \epsilon) \ni q$ も自然だと思います. 不自然なのは「なにも入力されない」ときにどこかへ遷移することもあるということです. たぶんもっと先に進めば, なにか $\epsilon$-遷移の必要性がわかるのかなとぼんやりと思っています.

　$\epsilon-N$ の受理条件を考えるために, ある状態から $\epsilon$-遷移をして到達できる範囲を定めるのは自然です. $\epsilon$-遷移はなんの入力もなしに, すなわち無条件に遷移することなので, たとえば状態 $q_{0}, q_{1}, q_{2}$ において $q_{0}$ から $q_{1}$ への $\epsilon$-遷移 $q_{0} \overset{\epsilon}{\to} q_{1}$ および $q_{1}$ から $q_{2}$ への $\epsilon$-遷移 $q_{1} \overset{\epsilon}{\to} q_{2}$ があったとき, $q_{0}$ は $\epsilon$-遷移によって $q_{2}$ まで到達することが可能です.
　これは非決定的な遷移としてみることができます. したがって, ある状態から $\epsilon$-遷移のみをいくつか繰り返して経て到達する状態の集合を定めておくと好ましいです.

　上の例では
$$ \begin{eqnarray*} \epsilon-\text{CL}(q_{0}) &=& \{ q_{0}, q_{1}, q_{2} \} \\ \epsilon-\text{CL}(q_{1}) &=& \{ q_{1}, q_{2} \} \\ \epsilon-\text{CL}(q_{2}) &=& \{ q_{2} \} \end{eqnarray*} $$
となります.

　これもちょっとした疑問で, でもあまり大事なことではないと思うのですが, $\epsilon-\text{CL}(q)$ を $\delta_{\epsilon}(q, \epsilon)$ を用いてどのように定義すればよいのでしょうか. たとえば $q_{2} \in \epsilon-\text{CL}(q_{0})$ である理由は, $q_{2} = \delta_{\epsilon}(\delta_{\epsilon}(q_{0}, \epsilon), \epsilon)$ からなのですが, これを一般的にどうして書けますか？ わたしがちらっと思ったのは, やはり $\delta_{\epsilon}$ の再帰と, $\epsilon-N$ が有限であるという仮定についてなのですが, わたしには難しいです.

　$\epsilon-N$ の受理条件について, 大切な気持ちは $\epsilon$-遷移と入力されるアルファベット $\sigma \in \Sigma$ による遷移によって, 受理状態の集合 $F$ に到達するということです. その path は, 次に述べる遷移のいずれかに当てはまります.
　初期状態 $q_{0}$ は $\sigma$ を読み取る前に無条件で $\epsilon$-遷移することがあり, その $\epsilon$-遷移によって到達できる状態の集合は $\epsilon-\text{CL}(q_{0})$ と表わされ, その後 $\epsilon-\text{CL}(q_{0})$ のおのおのの元が $\sigma$ を読み取って遷移した状態の集合
$$ \displaystyle \bigcup_{q \in \epsilon-\text{CL}(q_{0})} \delta_{\epsilon}(q, \sigma) $$
の, おのおのの元は再び $\epsilon$-遷移をし,
$$ \displaystyle \bigcup_{q \in \epsilon-\text{CL}(q_{0})} \epsilon-\text{CL}(\delta_{\epsilon}(q, \sigma)) $$
と表わせます.
　ここで, $\epsilon-\text{CL} : Q \to 2^{Q}$ であり, $\displaystyle \bigcup_{q \in \epsilon-\text{CL}(q_{0})} \delta_{\epsilon}(q, \sigma) \subset Q$ の像について,
$$ \epsilon-\text{CL} \left( \bigcup_{q \in \epsilon-\text{CL}(q_{0})} \delta_{\epsilon}(q, \sigma) \right) = \bigcup_{q \in \epsilon-\text{CL}(q_{0})} \epsilon-\text{CL} \left( \delta_{\epsilon} (q, \sigma) \right) $$
が成り立ちます. これを $\delta^{*}_{\epsilon}(\sigma)$ とおきます.
$$ \delta^{*}_{\epsilon}(\sigma) = \displaystyle \epsilon-\text{CL} \left( \bigcup_{q \in \epsilon-\text{CL}(q_{0})} \delta_{\epsilon} (q, \sigma) \right) $$

　これが$1$つめの記号 $\sigma \in \Sigma$ を読み取ったときの $\epsilon-N$ の状態です. 次に, $\tau \in \Sigma$ として $\sigma \tau$ をどのように読み込むのかというと, $\sigma$ を読み取ったあとの $\epsilon$-遷移は済んでいるので, はじめに $\epsilon$-閉包を取る必要はなく, たんに状態集合 $\delta^{*}_{\epsilon} (\sigma)$ のおのおのの元に $\tau$ を読み込ませて, そしてその状態集合の $\epsilon$-閉包をとればよいです. すなわち
$$ \delta^{*}_{\epsilon}(\sigma \tau) = \epsilon-\text{CL} \Biggl( \displaystyle \bigcup_{q \in \delta^{*}_{\epsilon} (\sigma)} \delta_{\epsilon} (q, \tau) \Biggr) $$
　これが $\epsilon-N$ に語 $\sigma \tau$ を与えたとき, 初期状態 $q_{0}$ から遷移する状態の集合となります.
　帰納的に, 語 $w = \sigma \tau, ~ \sigma \in \Sigma^{*}, \tau \in \Sigma$ に対して,
$$ \delta^{*}_{\epsilon}(w) = \epsilon-\text{CL} \Biggl( \bigcup_{q \in \delta^{*}_{\epsilon} (\sigma)} \delta_{\epsilon}(q, \tau) \Biggr) $$
とすると, $\delta_{\epsilon}^{*}(w)$ は語 $w$ を与えられた $\epsilon-N$ が初期状態 $q_{0}$ から遷移を経て到達する状態の集合となります. したがって, この $\delta^{*}_{\epsilon}(w)$ が受理状態の集合 $F$ と共通の元を持っているならば, 語 $w$ は受理されます.
　$w = \epsilon$ の特別な場合は $\delta^{*}_{\epsilon}(\epsilon) = \epsilon-\text{CL}(q_{0})$ とします. あとでも質問するのですが, こうする妥当な理由はあるでしょうか. 「妥当」かどうかはわかりませんが, こうするとたとえば $\sigma \in \Sigma$ として
$$ \delta_{\epsilon}^{*}(\sigma) = \epsilon-\text{CL} \Biggl( \bigcup_{q \in \delta_{\epsilon}^{*}(\epsilon)} \delta_{\epsilon} (q, \sigma) \Biggr) $$
と表わせます.
　$\epsilon$-非決定性有限オートマトン $\epsilon-N$ が受理する語の集合を $L(\epsilon-N)$ とすると,
$$ w \in L(\epsilon-N) \Leftrightarrow \delta^{*}_{\epsilon}(w) \cap F \neq \varnothing $$
　$\epsilon$-非決定性有限オートマトンが認識する言語のクラスを $\mathcal{L}_{\epsilon-\text{NFA}}$ と書きます. わたしが確認してほしいのは,

の証明です. $\mathcal{L}_{\text{NFA}} \subset \mathcal{L}_{\epsilon-\text{NFA}}$ は自明な $\epsilon$-遷移だけの $\epsilon$-非決定性有限オートマトンを考えれば成り立ちます.

　$^{*1}$ は恣意的な気がします. 定義$1$では $\delta_{N}^{*}(\epsilon) = \{ q_{0} \}$ としていたのに, 上の証明では $\delta_{N}^{*}(\epsilon) = \epsilon-\text{CL}(q_{0})$ としました. もし $\epsilon$-非決定性有限オートマトンが空列 $\epsilon$ を受理するとしたら(実際にそのような $\epsilon-N$ はつくれます), それを模倣しようとする非決定性有限オートマトンは $\epsilon$ を受理しますか？ でも, 非決定性有限オートマトンの遷移関数は $\epsilon$ を受けとることができないので, それは不可能だとわたしは思っています. それは模倣と言えるのでしょうか. よくわかりません. ただひとつ言えるのは, $\delta_{N}^{*}(\epsilon) = \epsilon-\text{CL}(q_{0})$ とすれば, $1$つ以上の記号 $\sigma \in \Sigma$ に関して $\delta_{N}^{*}(\sigma) = \delta_{\epsilon}^{*}(\sigma)$ は成り立つ, ということです.

　$^{*2}$ はうまく言葉にすることができません. 言葉にすることができないということはまちがっているのかもしれません. もしここがまちがっているとすれば, わたしの証明はまちがっています. 気持ちとしては, $P$ の $\epsilon$-閉包の元である $q$ の, さらに $\epsilon$-閉包をとってもなにも変わりません. なぜならば $\epsilon$-遷移で行き着く先をすべて取り上げたのが $\epsilon$-閉包なのですから. $q$ の $\epsilon$-閉包の元である $p$ が $P$ の $\epsilon$-閉包の元ではないということはありません. $p$ が動き得るのは, すでに $P$ の $\epsilon$-閉包のすべて, そしてそれのみです. これを形式的に書きたかったのですが, うまくいきませんでした.

　誰かやさしいひとがこれを証明してくれるか, あるいは否定してくれるのを待っています. ありがとうございました.