決定性有限オートマトンと非決定性有限オートマトンがそれぞれ認識する言語のクラスが一致することについて
ひとつの命題を理解するために, わたしは五日もかけてしまっています. わたしにはあまり時間がないのと, 精神力がないために, 不十分な理解のまま質問をしてしまうことを許してください. わたしが理解できていないのは, 決定性有限オートマトンと非決定性有限オートマトンが認識する言語のクラスが一致する, という命題です. たぶんわたしの質問に答えてくださる方はすでにそれらのことごとをよく知っているのだと思いますが, すこし抽象的な質問にもなると思うので, それらのことごとを知らない方も, わたしは以下で必要なだけ定義を書くので, もしよかったら考えてみてください. よろしくお願いします.
決定性有限オートマトン $M$ とは 5 つの組 $\langle Q, \Sigma, \delta, q_{0}, F \rangle$ である. ここで $\delta$ は $Q \times \Sigma$ から $Q$ への写像, また $q_{0}$ は $Q$ の特別な元であり, $F$ は $Q$ の部分集合である. $Q, \Sigma, (F)$ はいずれも有限集合である.
$\Sigma$ のいくつかの元を並べた列の集合を $\Sigma^{*}$ と書き, その元を語と呼ぶ. それは $0$ 個の $\Sigma$ の元の列である空列 $\epsilon$ をも含むとする.
決定性有限オートマトン $M = \langle Q, \Sigma, \delta, q_{0}, F \rangle$ が語 $w_{1}w_{2} \cdots w_{n} = w \in \Sigma^{*}$ を受理するとは, $\delta$ による計算の列
$$
\begin{eqnarray*}
\delta (q_{0}, w_{1}) &=& q_{1} \\
\delta (q_{1}, w_{2}) &=& q_{2} \\
& \vdots & \\
\delta (q_{n - 1}, w_{n}) &=& q_{n}
\end{eqnarray*}
$$
において $q_{n} \in F$ であることを言う($\delta$ の定義からおのおのの $q_{i}$ は $Q$ の元であって, 重複することもある). $M$ が受理する語の集合を $L(M)$ と書いて, $M$ は $L(M)$ を認識するという. 決定性有限オートマトンが認識する言語のクラスを $\mathcal{L}_{\text{DFA}}$ と書く.
上の $\delta$ による計算の列は次の帰納的に定義される(「実行」のような) 関数で表現することもできます.
決定性有限オートマトン $M = \langle Q, \Sigma, \delta, q_{0}, F \rangle$ に対して, 関数 $\delta^{*} : Q \times \Sigma^{*} \to Q$ を次のように定義する. $q \in Q$, $w \in \Sigma^{*}$ として,
$$
\delta^{*} (q, w) =
\begin{cases}
q & (w = \epsilon) \\
\delta (\delta^{*} (q, x), y) & (w = xy, x \in \Sigma^{*}, y \in \Sigma)
\end{cases}
$$
こう定義した $\delta^{*}$ を用いると, 上の $\delta$ の計算列と受理条件はもっと簡単に
$$
\delta^{*} (q_{0}, w) \in F
$$
と表現できます. つまり
$$
w \in L(M) \Leftrightarrow \delta^{*} (q_{0}, w) \in F
$$
次に非決定性有限オートマトンを定義します.
非決定性有限オートマトン $N$ とは 5 つの組 $\langle Q, \Sigma, \delta, q_{0}, F \rangle$ である. ここで $\delta$ は $Q \times \Sigma$ から $2^{Q}$ への写像であり, この終域が $Q$ の冪集合という点において「非」決定性を持つ. その他は同じく, $Q, \Sigma, (F)$ は有限集合である.
非決定性有限オートマトン $N = \langle Q, \Sigma, \delta, q_{0}, F \rangle$ が語 $w_{1}w_{2} \cdots w_{n} = w \in \Sigma^{*}$ を受理するとは, ある $Q$ の元の列 $q_{0}, q_{1}, \cdots, q_{n}$ が存在して,
$$
\begin{eqnarray*}
\delta(q_{0}, w_{1}) &\ni& q_{1} \\
\delta(q_{1}, w_{2}) &\ni& q_{2} \\
&\vdots& \\
\delta(q_{n - 1}, w_{n}) &\ni& q_{n}
\end{eqnarray*}
$$
を満たし, $q_{n} \in F$ であることをいう.
言い下せば, $\delta$ による計算において, 非決定性ゆえにたくさんの道が存在します. その複数の道には $F$ に到達しない道もありますし, そもそも $\delta$ の像が空集合となって計算が終了してしまう道もあります. そのなかで $F$ の元に到達する道がひとつでもあれば受理するということになります. これだとわかりにくいので, 先の決定性有限オートマトンにおいて実行を表現した $\delta^{*}$ を, この非決定性有限オートマトンにも適用してみます.
非決定性有限オートマトン $N = \langle Q, \Sigma, \delta, q_{0}, F \rangle$ に対して, 関数 $\delta^{*} : 2^{Q} \times \Sigma^{*} \to 2^{Q}$ を次のように帰納的に定義する. $q \subset Q$, $w \in \Sigma^{*}$ として,
$$
\delta^{*} (q, w) =
\begin{cases}
q & (w = \epsilon) \\
\displaystyle \bigcup_{q' \in \delta^{*} (q, x)} \delta (q', y) & (w = xy, x \in \Sigma^{*}, y \in \Sigma)
\end{cases}
$$
こうすると,
$$
w \in L(N) \Leftrightarrow \delta^{*} (\{ q_{0} \}, w) \cap F \neq \varnothing
$$
と簡単になります. 最後に,
非決定性有限オートマトン $N$ が受理する語の集合を $L(N)$ と書いて, $N$ は $L(N)$ を認識するといい, 非決定性有限オートマトンが認識する言語のクラスを $\mathcal{L}_{\text{NFA}}$ と書く.
わたしが理解できない命題というのは,
$\mathcal{L}_{\text{DFA}} = \mathcal{L}_{\text{NFA}}$
です. $\mathcal{L}_{\text{DFA}} \subset \mathcal{L}_{\text{NFA}}$ はほとんど明らかなのですが, 一応形式的に証明してみます.
$\mathcal{L}_{\text{DFA}} \subset \mathcal{L}_{\text{NFA}}$
決定性有限オートマトン $M = \langle Q, \Sigma, \delta_{M}, q_{0}, F \rangle$ に対して $N$ を, $\langle Q, \Sigma, \delta_{N}, q_{0}, F \rangle$, ただし
$$
\delta_{N} (q, \sigma) = \{ \delta_{M} (q, \sigma) \} \quad (\sigma \in \Sigma)
$$
とすると, $N$ は非決定性有限オートマトンとなる. このとき任意の $w \in \Sigma^{*}$ に対して
$$
\delta_{N}^{*}(\{q_{0}\}, w) = \{ \delta_{M}^{*}(q_{0}, w)\}
$$
となることを帰納的に示す. まず $w = \epsilon$ のときは
$$
\delta_{N}^{*} (\{ q_{0} \}, \epsilon) = \{ q_{0} \} = \{ \delta_{M}^{*} (q_{0}, \epsilon) \}
$$
となって正しい. $w = xy, ~ x \in \Sigma^{*}, y \in \Sigma$ のとき,
$$
\begin{eqnarray*}
\delta_{N}^{*} (\{ q_{0} \}, w) &=& \displaystyle \bigcup_{q' \in \delta_{N}^{*}(\{q_{0}\}, x)} \delta_{N} (q', y) \\
&=& \displaystyle \bigcup_{q' \in \{ \delta^{*}(q_{0}, x)\}} \delta_{N} (q', y) \quad (\text{帰納法の仮定より})\\
&=& \delta_{N} (\delta^{*}(q_{0}, x), y) \\
&=& \{ \delta (\delta^{*}(q_{0}, x), y) \} \\
&=& \{ \delta^{*} (q_{0}, w) \}
\end{eqnarray*}
$$
このことから, $w \in L(M) \Leftrightarrow \delta_{M}^{*}(q_{0}, w) \in F$ のとき, $\delta_{N}^{*}(\{ q_{0} \}, w) = \{ \delta_{M}^{*}(q_{0}, w)\} \subset F$ であるので, $\delta_{N}^{*} (\{q_{0}\}, w) \cap F \neq \varnothing \Leftrightarrow w \in L(N)$.
たしかめる必要があるのかわかりませんが, $w \notin L(M)$ のときは, $\delta_{M}^{*}(q_{0}, w) \notin F$ となって, $\delta_{N}^{*} (\{ q_{0}\}, w) = \{ \delta_{M}^{*} (q_{0}, w) \} \not\subset F$ より $\delta_{N}^{*}(\{ q_{0} \}, w) \cap F = \varnothing$ となります. でも考えてみると同値なのだからたしかめるまでもないのですが, 受理する語は受理して, 受理しない語は受理してほしくないという気持ちは落ち着きます.
そしてわたしの疑問は
$\mathcal{L}_{\text{NFA}} \subset \mathcal{L}_{\text{DFA}}$
にあります. 命題2のように, 非決定性有限オートマトンを模倣する, すなわち認識する言語が等しくなるような決定性有限オートマトンを構成できればこれは解決されます. 先に紹介した関数で, 次の証明のうちに現れるものをあらためて整理します. まず, 決定性有限オートマトンの(遷移)関数 $\delta : Q \times \Sigma \to Q$ に対して,
$$
\delta^{*}(q, w) =
\begin{cases}
q & (w = \epsilon) \\
\delta (\delta^{*}(q, x), y) & (w = xy, x \in \Sigma^{*}, y \in \Sigma)
\end{cases}
$$
遷移関数 $\delta$ は $\delta : Q \times \Sigma \to Q$ と, $\Sigma$ の元を受け取るのに対して, $\delta^{*}$ は $\delta^{*} : Q \times \Sigma^{*} \to Q$ と, $\Sigma^{*}$, すなわち $\Sigma$ の元の列を受け取ります. 次に, 非決定性有限オートマトンの遷移関数 $\delta : Q \times \Sigma \to 2^{Q}$ に対して,
$$
\delta^{*} (S, w) =
\begin{cases}
S & (w = \epsilon) \\
\displaystyle \bigcup_{q \in \delta^{*}(S, x)} \delta(q, y) & (w = xy, x \in \Sigma^{*}, y \in \Sigma)
\end{cases}
$$
ここで $S \in 2^{Q}$, すなわち $S \subset Q$ です. 非決定性有限オートマトンの遷移関数は $\delta : Q \times \Sigma \to 2^{Q}$ というかたちをしているのに対して, $\delta^{*}$ は $\delta^{*} : 2^{Q} \times \Sigma^{*} \to 2^{Q}$ というかたちをしています. なぜ $Q \times \Sigma^{*} \to 2^{Q}$ ではないのかを考えてみると, この関数 $\delta^{*}$ は計算を実行するにあたって帰納的な性質を持っているからだと言えると思います. 適切ではない書き方ですが,
$$
\delta^{*} :
\begin{cases}
Q \times \Sigma^{*} \to Q & (\text{決定性}) \\
2^{Q} \times \Sigma^{*} \to 2^{Q} & (\text{非決定性})
\end{cases}
$$
に留意します.
$N = \langle Q, \Sigma, \delta_{N}, q_{0}, F \rangle$ を非決定性有限オートマトンとする. $N$ を模倣するような決定性有限オートマトン $M = \langle Q_{M}, \Sigma_{M}, \delta_{M}, q_{0M}, F_{M} \rangle$ を次のように構成する.
$Q_{M} = 2^{Q}$, $\Sigma_{M} = \Sigma$, $q_{0M} = \{ q_{0} \}$, $\delta_{M} : 2^{Q} \times \Sigma \to 2^{Q}$
$$
\delta_{M} (S, w) \stackrel{\text{def}}{=} \bigcup_{q \in S} \delta_{N} (q, w)
$$
$$
F_{M} \stackrel{\text{def}}{=} \{ S \subset Q \mid S \cap F \neq \varnothing \}
$$
このとき, $\delta_{M}^{*}$ は $\delta_{M}^{*} : Q_{M} \times \Sigma^{*} \to Q_{M}$ すなわち $2^{Q} \times \Sigma^{*} \to 2^{Q}$であり,
$$
\delta_{M}^{*} (S, w) =
\begin{cases}
S & (w = \epsilon) \\
\delta_{M} (\delta_{M}^{*} (S, x), y) & (w = xy, x \in \Sigma^{*}, y \in \Sigma)
\end{cases}
$$
である.
任意の $w \in \Sigma^{*}$ に関して, $\delta_{M}^{*}(\{ q_{0} \}, w) = \delta_{N}^{*} (\{ q_{0}\}, w)$ が成り立つことを帰納的に示す. $w = \epsilon$ のときは定義から, $\delta_{M}^{*} (\{ q_{0} \}, \epsilon) = \{ q_{0} \} = \delta_{N}^{*}(\{ q_{0} \}, \epsilon)$ となって正しい. $w = xy \in \Sigma^{*}, ~ x \in \Sigma^{*}, y \in \Sigma$ として,
$$
\begin{eqnarray*}
\delta_{M}^{*}(\{q_{0}\}, w) &=& \delta_{M}(\delta_{M}^{*}(\{q_{0}\}, x), y) \quad (\delta_{M}^{*} \text{の定義より})\\
&=& \delta_{M}(\delta_{N}^{*}(\{q_{0}\}, x), y) \quad (\text{帰納法の仮定より}) \\
&=& \displaystyle \bigcup_{q \in \delta_{N}^{*}(\{q_{0}\}, x)} \delta_{N}(q, y) \quad (\delta_{M}\text{の定義より}) \\
&=& \delta_{N}^{*}(\{q_{0}\}, xy) \quad (\delta_{N}^{*} \text{の定義より})\\
&=& \delta_{N}^{*}(\{q_{0}\}, w)
\end{eqnarray*}
$$
いま, $w \in L(N)$ とすると, $\delta_{N}^{*}(\{q_{0}\}, w) \cap F \neq \varnothing$ である. $\delta_{N}^{*}(\{q_{0}\}, w)$ と等しい $\delta_{M}^{*}(\{q_{0}\}, w)$ は従って $F$ と交わるから, $F_{M}$ の定義によって, $\delta_{M}^{*}(\{q_{0}\}, w) \in F_{M}$. よって $w \in L(M)$
わたしの疑問は, どうやってここまで来たのか, ということです. 模倣である決定性有限オートマトンにおいて, どうやって $Q_{M}$ を $2^{Q}$ とおこうと思ったのか, どうして $\delta_{M}(S, w) = \bigcup_{q \in S} \delta_{N}(q, w)$ としようと思ったのか, なぜ $F_{M}$ を $F$ と交わるような $Q$ の部分集合族としようとしたのか, そこまで辿り着く道がよくわからないのです.
すこし眺めてみると, 語 $w$ が受理される条件は, 決定性有限オートマトンでは $\delta_{M}^{*}(q_{0}, w) \in F$, 非決定性では $\delta_{N}^{*}(\{q_{0}\}, w) \cap F \neq \varnothing$ となっていて, ふたつのオートマトンの認識する言語が等しくなってほしい思いは
$$
[ \delta_{M}^{*}(q_{0}, w) \in F_{M} ] \Leftrightarrow [\delta_{N}^{*}(\{q_{0}\}, w) \cap F_{N} \neq \varnothing]
$$
というかたちで表わされます. するとぼんやりと $F_{M} \stackrel{\text{def}}{=} \{ S \subset Q \mid S \cap F \neq \varnothing \}$ が見えてきます. でも, それがはっきりとは見えないことは, $\delta_{M}^{*}(\{q_{0}\}, w) = \delta_{N}^{*}(\{q_{0}\}, w)$ としようとした心がわからないからなのだと思いました.
たしかに, $\delta_{M}^{*}(\{q_{0}\}, w) = \delta_{M}^{*}(\{q_{0}\}, w)$ としようとする気持ちを認めれば, このような $F_{M}$ の定義はとても自然です. それに, 証明のなかで現れた $\delta_{M}$ の定義
$$
\delta_{M}(S, w) = \bigcup_{q \in S} \delta_{N}(q, w) \quad \cdots (*)
$$
も自然です. なぜならば $w = xy, ~ x \in \Sigma^{*}, y \in \Sigma$ なる語に対して,
$$
(1) \quad \delta_{M}^{*}(S, w) = \delta_{M}(\delta_{M}^{*}(S, x), y) \quad (\text{決定性})
$$
と,
$$
(2) \quad \delta_{N}^{*}(S, w) = \bigcup_{q \in \delta_{N}^{*}(S, x)} \delta_{N}(q, y) \quad (\text{非決定性})
$$
とを一致させたいと思ったときに, 帰納法の仮定として $\delta_{M}^{*}(S, x) = \delta_{N}^{*}(S, x)$ だとして(たとえば $\epsilon$ を考えてみる), それを $P$ とおくと 上の (1), (2) が等しいことは
$$
\delta_{M}(P, y) = \bigcup_{q \in P} \delta_{N}(q, y)
$$
と表わせるからです. そして, 表現がうまくないのですが, そうして定義すると, 「非決定性」の性質が「決定的」に捉えられるのです. たとえば非決定性有限オートマトン $N$ において, その遷移関数 $\delta_{N}$ が
$$
\delta_{N}(q_{0}, 0) = \{ q_{0}, q_{1} \}
$$
だったときに, 次に $1 \in \Sigma$ を読み取るとすると, そのステップは
$$
\delta_{N}(q_{0}, 1) \cup \delta_{N}(q_{1}, 1)
$$
となって, これは
$$
\delta_{M}(\{q_{0}, q_{1}\}, 1) = \bigcup_{q \in \{q_{0}, q_{1}\}} \delta_{N}(q, 1)
$$
とも表わせるからです.
とにかくわたしにはよくわかりません. 模倣するオートマトンを構成するということが,
$$
[\delta_{M}(\{q_{0}\}, w) \in F_{M}] \Leftrightarrow [\delta_{N}(\{q_{0}\}, w) \cap F_{N} \neq \varnothing]
$$
を満たす $\delta_{M}, F_{M}$ を求めることであることと,
$$
\delta_{M}^{*}(\{q_{0}\}, w) = \delta_{N}^{*}(\{q_{0}\}, w)
$$
がそのひとつの答えであることと, 特に, この答えが模倣に関して自然な考え方だということがわかりません. たぶん,
$$
\delta_{M}(S, \sigma) = \bigcup_{q \in S} \delta_{N}(q, \sigma)
$$
が模倣ということの鍵となるのだと思います. だから, わたしは「模倣」がよくわかっていないのだと思います. なにを質問したいかもわたし自身よくわかっていません. この,
$$
[\delta_{M}(\{q_{0}\}, w) \in F_{M}] \Leftrightarrow [\delta_{N}(\{q_{0}\}, w) \cap F_{N} \neq \varnothing]
$$
とか,
$$
\delta_{M}^{*}(\{q_{0}\}, w) = \delta_{N}^{*}(\{q_{0}\}, w)
$$
とか,
$$
\delta_{M}(S, \sigma) = \bigcup_{q \in S} \delta_{N}(q, \sigma)
$$
とかの関係について教えてほしいです. たぶん
$$
\delta_{M}(S, \sigma) = \bigcup_{q \in S} \delta_{N}(q, \sigma)
$$
ならば
$$
[\delta_{M}(\{q_{0}\}, w) \in F_{M}] \Leftrightarrow [\delta_{N}(\{q_{0}\}, w) \cap F_{N} \neq \varnothing]
$$
となるとは思うのですが, 逆は成り立ちますか? ぐちゃぐちゃな質問でごめんなさい. 疲れました. 堂々巡りになってしまいます. よろしくお願いします.
追記 4月26日
模倣する決定性有限オートマトンを構成するという点において, これは方程式のような雰囲気がします. ある非決定性有限オートマトンを模倣する決定性有限オートマトンを構成することは可能であることはたしかです, ──実際に, 構成できていますから. つまりこの方程式には解があります. でも, もし $\delta_{M}(S, \sigma) = \bigcup_{q \in S} \delta_{N}(q, \sigma)$ というのが単なるアイデアであって, もしそれが見つけられなかったら, 構成することはできるけれども実際にどのように構成すればよいのかわからなかったら, すなわち, 方程式に解が存在することが示せても, 具体的にその解を求めることができなかったら, わたしは何を語ることができるのでしょうか. その意味で, $\delta_{M}(S, \sigma) = \bigcup_{q \in S} \delta_{N}(q, \sigma)$ が $M$ が $N$ を模倣するという点で必要であってほしいと願い, そのことを理解したいのです.