文献あり

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

261

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

　非決定性有限オートマトン $N$ は, $5$つの組 $\langle Q, \Sigma, \delta_{N}, q_{0}, F \rangle$ である. $Q$ は状態の集合, $\Sigma$ は入力される記号の集合, $\delta_{N}$ は遷移関数と呼ばれる, $Q \times \Sigma \to Q$ という関数, $q_{0}$ は $Q$ の特別な元で, 初期状態と呼ばれ, $F$ は $Q$ の部分集合で, 受理状態の集合である.
　入力される記号の集合 $\Sigma$ のいくつかの列の集合を $\Sigma^{*}$ と書き, その元を語と呼ぶ. $0$個の列の場合, それを $\epsilon$ と表わす.
　遷移関数 $\delta_{N}$ に対して $\delta^{*}_{N}$ を考える. これは $\Sigma^{*}$ から $2^{Q}$ への写像であって, 次のように帰納的に定義される. $w \in \Sigma^{*}$ として,
$$ \delta^{*}_{N}(w) = \begin{cases} \{ q_{0} \} & (w = \epsilon) \\[8pt] \displaystyle \bigcup_{q \in \delta^{*}_{N}(\tau)} \delta_{N}(q, \sigma) & (w = \tau \sigma, ~ \tau \in \Sigma^{*}, \sigma \in \Sigma) \end{cases} $$
　非決定性有限オートマトン $N$ が語 $w = w_{0}w_{1} \cdots w_{n} \in \Sigma^{*}$ を受理するとは, ある状態の集合(すなわち $Q$ の部分集合) の列 $Q_{0}, Q_{1}, \cdots, Q_{n}$ が存在して, 遷移関数 $\delta_{N}$ による計算の列
$$ \begin{eqnarray*} \delta_{N}(q_{0}, w_{0}) &=& Q_{0} \\ \bigcup_{q \in Q_{0}} \delta_{N}(q, w_{1}) &=& Q_{1} \\ &\vdots& \\ \bigcup_{q \in Q_{n - 1}} \delta_{N}(q, w_{n}) &=& Q_{n} \end{eqnarray*} $$
において, $Q_{n}$ が受理状態の集合 $F$ と共通の元を持つ, すなわち $Q_{n} \cap F \neq \varnothing$ が成り立つことをいう. これは $\delta^{*}_{N}$ を用いて, $\delta^{*}_{N}(w) \cap F \neq \varnothing$ と表わせる.
　非決定性有限オートマトン $N$ が受理する語の集合を $L(N)$ と表わして $N$ は $L(N)$ を認識するといい, 非決定性有限オートマトンが認識する言語のクラスを $\mathcal{L}_{\text{NFA}}$ と表わす.

　先の記事では $\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} \}$ としました. これはちょっとした質問なのですが, このように定義することでなにか具合のわるいことが起きるでしょうか.

　$\epsilon$-非決定性有限オートマトン $\epsilon-N$ は$5$つの組 $\langle Q, \Sigma, \delta_{\epsilon}, q_{0}, F \rangle$ である. $Q, \Sigma, q_{0}, F$ は非決定性有限オートマトンと同様である. $\delta_{\epsilon}$ は $Q \times (\Sigma \cup \{ \epsilon\})$ から $2^{Q}$ への写像であって, 特に $\delta_{\epsilon}(q, \epsilon)$ による遷移を $\epsilon$-遷移と呼ぶ.

　実を言うと, よくわかっていません. 入力が与えられたときに状態が遷移することは自然なふうに思えます. 一方で「なにも入力されない」ことで「動かない」というのもひとつの遷移と考えられると思えば $\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$-遷移のみをいくつか繰り返して経て到達する状態の集合を定めておくと好ましいです.

　$q \in Q$ に対して, $\epsilon$-遷移のみをいくつか繰り返して経て到達できる状態の集合を $q$ の $\epsilon$-閉包と呼び, $\epsilon-\text{CL}(q)$ と表わす.

　上の例では
$$ \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}} = \mathcal{L}_{\epsilon-\text{NFA}} $$

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

$$ \mathcal{L}_{\epsilon-\text{NFA}} \subset \mathcal{L}_{\text{NFA}} $$

　$\epsilon-N = \langle Q, \Sigma, \delta_{\epsilon}, q_{0}, F \rangle$ を $\epsilon$-非決定性有限オートマトンとし, それに対して $N = \langle Q, \Sigma, \delta_{N}, q_{0}, F \rangle$
$$ \delta_{N}(q, \sigma) = \epsilon-\text{CL} ~ \Biggl( \bigcup_{q' \in \epsilon-\text{CL}(q)} \delta_{\epsilon}(q', \sigma) \Biggr) $$
なる非決定性有限オートマトンが $\epsilon-N$ を模倣すること, すなわち, 上で定めた受理を判定する関数
$$ \delta^{*}_{\epsilon}(w) = \begin{cases} \epsilon-\text{CL}(q_{0}) & (w = \epsilon) \\[8pt] \epsilon-\text{CL} \Biggl( \displaystyle \bigcup_{q \in \delta^{*}_{\epsilon}(\sigma)} \delta_{\epsilon}(q, \tau)\Biggr) & (w = \sigma \tau, ~ \sigma \in \Sigma^{*}, \tau \in \Sigma) \\ \end{cases} $$
と, 模倣遷移関数 $\delta_{N}$ による判定関数
$$ \delta_{N}^{*}(w) = \begin{cases} \epsilon-\text{CL}(q_{0}) & (w = \epsilon) \\[8pt] \displaystyle \bigcup_{q \in \delta_{N}^{*}(\sigma)} \delta_{N} (q, \tau) & (w = \sigma \tau, ~ \sigma \in \Sigma^{*}, \tau \in \Sigma) \end{cases} $$
とが等しいことを示す. ただし
$$ \delta^{*}_{N}(\epsilon) = \epsilon-\text{CL}(q_{0}) $$
としている. $^{*1}$
　語 $\sigma_{0}\sigma_{1} \cdots \sigma_{n}$　が与えられたとき, 遷移関数 $\delta_{\epsilon}$ による遷移過程に現れる状態の集合 $P_{n}$ を次のように帰納的に定める.
$$ P(0) = \displaystyle \bigcup_{q \in \epsilon-\text{CL}(q_{0})} \delta_{\epsilon}(q, \sigma_{0}) $$
$$ P(n) = \displaystyle \bigcup_{q \in \epsilon-\text{CL}(P_{n - 1})} \delta_{\epsilon}(q, \sigma_{n}) $$
　このとき,
$$ \begin{eqnarray*} \delta_{\epsilon}^{*}(\sigma_{0}) &=& \epsilon-\text{CL} \Biggl( \bigcup_{q \in \epsilon-\text{CL}(q_{0})} \delta_{\epsilon}(q, \sigma_{0}) \Biggr) \\[8pt] &=& \epsilon-\text{CL}(P_{0}) \end{eqnarray*} $$
であり, $n \in \mathbb{N}$ について $\delta_{\epsilon}^{*}(\sigma_{0} \cdots \sigma_{n}) = \epsilon-\text{CL}(P_{n})$ と仮定すると
$$ \begin{eqnarray*} \delta_{\epsilon}^{*}(\sigma_{0} \cdots \sigma_{n}\sigma_{n + 1}) &=& \epsilon-\text{CL} \Biggl( \bigcup_{q \in \delta_{\epsilon}^{*}(\sigma_{0} \cdots \sigma_{n})} \delta_{\epsilon}(q, \sigma_{n + 1})\Biggr) \\ &=& \epsilon-\text{CL} \Biggl( \bigcup_{q \in \epsilon-\text{CL}(P_{n})} \delta_{\epsilon}(q, \sigma_{n + 1})\Biggr) \\ &=& \epsilon-\text{CL}(P_{n + 1}) \end{eqnarray*} $$
　この $\sigma_{0} \cdots \sigma_{n}$ に依存する遷移過程の状態集合 $P_{n}$ を用いて $\delta_{\epsilon}^{*}(\sigma_{0} \cdots \sigma_{n})$ は
$$ \delta_{\epsilon}^{*}(\sigma_{0} \cdots \sigma_{n}) = \epsilon-\text{CL} \Biggl( \bigcup_{q \in \epsilon-\text{CL}(P_{n - 1})} \delta_{\epsilon}(q, \sigma_{n}) \Biggr) = \epsilon-\text{CL}(P_{n}) $$
と表わせる.
　ところで, $w = \sigma \tau, ~ \sigma \in \Sigma^{*}, \tau \in \Sigma$ について, 定義から
$$ \begin{eqnarray*} \delta_{N}^{*}(w) &=& \displaystyle \bigcup_{q \in \delta_{N}^{*}(\sigma)} \delta_{N}(q, \tau) \\ &=& \bigcup_{q \in \delta_{N}^{*}(\sigma)} \epsilon-\text{CL} \Biggl( \bigcup_{p \in \epsilon-\text{CL}(q)} \delta_{\epsilon}(p, \tau) \Biggr) \\ &=& \epsilon-\text{CL} \Biggl( \bigcup_{q \in \delta_{N}^{*}(\sigma)} \bigcup_{p \in \epsilon-\text{CL}(q)} \delta_{\epsilon}(p, \tau) \Biggr) \end{eqnarray*} $$
である. もし $\delta_{\epsilon}^{*}(\sigma) = \delta_{N}^{*}(\sigma)$ が成り立つならば, これは
$$ \delta_{N}^{*}(w) = \epsilon-\text{CL} \Biggl( \bigcup_{q \in \delta_{\epsilon}^{*}(\sigma)} \bigcup_{p \in \epsilon-\text{CL}(q)} \delta_{\epsilon}(p, \tau) \Biggr) $$
となる. $\delta_{\epsilon}^{*}(\sigma)$ はある状態集合の $\epsilon$-閉包として表わせるから, それを $P$ とおくと,
$$ \delta_{N}^{*}(w) = \epsilon-\text{CL} \Biggl( \bigcup_{q \in \epsilon-\text{CL}(P)} \bigcup_{p \in \epsilon-\text{CL}(q)} \delta_{\epsilon}(p, \tau) \Biggr) $$
　この式において, $p$ は状態 $q$ からの $\epsilon$-遷移で到達する状態であり, $q$ は状態集合 $P$ のある元から $\epsilon$-遷移で到達できる状態である. $^{*2}$
　したがって上の式は
$$ \epsilon-\text{CL} \Biggl( \bigcup_{q \in \epsilon-\text{CL}(P)} \delta_{\epsilon} (q, \tau) \Biggr) = \epsilon-\text{CL} \Biggl( \bigcup_{q \in \delta_{\epsilon}^{*} (\sigma)} \delta_{\epsilon}(q, \tau) \Biggr) = \delta_{\epsilon}^{*}(w) $$
と等しい.

　$^{*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$-閉包のすべて, そしてそれのみです. これを形式的に書きたかったのですが, うまくいきませんでした.