オートマトン

http://dnagarden.hgc.jp/miyano/ja/lib/exe/fetch.php?media=20081219report.pdf

今から10年以上前に解いた形式言語理論のレポート課題です。当時はなぜかこのレポート課題の問4.に強い興味を持ち、冬休みの6割くらいをこのレポート課題に当てました。授業の担当教授からは下記の解答案とは別のものが解答例として示されましたが、授業後に個人的に下記解答案を見せたところ、かなりびっくりした顔をされたあと、この方法でも正解だと言ってもらえました。

ただ、授業ではレポートを提出しているか把握されただけで、中身を精査してもらえたわけではないので、下記の解答案には論理の詰めが甘い部分が散見していると思います。誰かにブラッシュアップしてもらえることを願ってこの記事を書いておこうと思います。


(問4.)次の問題を解くアルゴリズムについて論じよ。

 入力:決定性有限オートマトン M_{1} = \left( Q_{1} , \Sigma , \delta_{1} , q_{0}^{1} , F_{1} \right)M_{2} = \left( Q_{2} , \Sigma , \delta_{2} , q_{0}^{2} , F_{2} \right)

 問題:L \left( M_{1} \right) = L \left( M_{2} \right) ならば "yes" を出力し、そうでなければ "no" を出力する。


解答案

M= \left( Q , \Sigma , \delta , q_{0} , F \right) は決定性有限オートマトンで、M の全ての状態は初期状態から到達可能であるとする。

このとき、次のようなアルゴリズムを用いて定義される決定性有限オートマトン M^{\mu} = \left( Q^{\mu} , \Sigma , \delta^{\mu} , q_{0}^{\mu} , F^{\mu} \right) は、L(M) を受理する最小オートマトンとなっている。


\begin{aligned}
& \textrm{begin} \\
& \quad \textrm{MarkedList} \leftarrow \left\{(p,q) | p \in F, q \in Q-F \right\}; \\
& \quad \textrm{UnMarkedList} \leftarrow F \times F \cup (Q-F) \times (Q-F) ; \\
& \quad \textrm{while} \\
& \quad \quad ある記号 a \in \Sigma と、ある組 (p,q) \in \textrm{UnMarkedList} が存在して \\
& \quad \quad \left(\delta(p,a),\delta(q,a) \right) \in \textrm{MarkedList}となっている. \\
& \quad \quad \quad \textrm{then} \\
& \quad \quad \quad \quad \textrm{begin} \\
& \quad \quad \quad \quad \quad \textrm{MarkedList} \leftarrow \{ (p,q) \} \cup \textrm{MarkedList}; \\
& \quad \quad \quad \quad \quad \textrm{UnMarkedList} \leftarrow \textrm{UnMarkedList} - \{ (p,q) \}; \\
& \quad \quad \quad \quad \textrm{end.} \\
& \textrm{end.}
\end{aligned}


このとき、UnMarkedListに入った (p,q) は、p \equiv_{M} q が成り立っている。 そこで、 \lbrack q \rbrack _{ \equiv _{M} } を、Q 上の同値関係 \equiv_{M} のもとでの q を含む同値類とすれば


\begin{aligned}
& \cdot \quad Q^{\mu} = \{ \, \lbrack q \rbrack _{\equiv _{M} }  | \, q \in Q \, \} \\
& \cdot \quad \delta^{\mu} \left( \lbrack q \rbrack _{ \equiv_{M}} , a \right) = \left \lbrack \delta(q,a) \right \rbrack _{ \equiv M} \quad \left( \lbrack q \rbrack _{\equiv _{M} } \in Q^{\mu} , a\in \Sigma \right) \\
& \cdot \quad q_0^{\mu} = \lbrack q_0 \rbrack _{ \equiv_{M}} \\
& \cdot \quad F^{\mu} = \{ \, \lbrack q \rbrack _{\equiv _{M} }  | \, q \in F \, \}
\end{aligned}


以上のアルゴリズムを用いて、決定性有限オートマトン M_1 , M_2に対し、最小オートマトン M_1^{\prime} , M_2^{\prime} を構成する。

このとき、L(M_1) = L(M_1^{\prime}) , L(M_2) = L(M_2^{\prime}) なので、L(M_1^{\prime}) = L(M_2^{\prime}) を判定するアルゴリズムを考えればよい。以下、その様なアルゴリズムを示す。ただし、M_1^{\prime} = \left( Q_{1} , \Sigma , \delta_{1} , q_{0} , F_{1} \right) , M_2^{\prime} = \left( Q_{2} , \Sigma , \delta_{2} , p_{0} , F_{2} \right) とする。


\begin{aligned}
\rm(\hspace{.18em}i\hspace{.18em}) \quad & |Q_1|\neq |Q_2| \, のとき \quad \quad "no"を出力する。 \quad&\rightarrow end. \\
\rm(\hspace{.08em}ii\hspace{.08em}) \quad & |Q_1| = |Q_2| = N + 1 \, より \\
& q_i \in Q_1 \quad (0 \le i \le N ) \quad に対し、次のように \, p_i \in Q_2 を定義する \\
& i=0のとき、 \quad p_i = p_0 \\
& i \neq 0 のとき、 \quad 文字数 N+1以下で q_i =\delta_1^{\star} (p_0 , x_i ) なる記号列 x_i を1つとる。 \\
& このとき p_i = \delta_2^{\star} (p_0 , x_i ) とする。\\
& ある 0 \le i \lt j \le N に対して、 p_i = p_j のとき、 "no"を出力する。 \quad &\rightarrow end. \\
\rm(i\hspace{-.08em}i\hspace{-.08em}i) \quad & (q_i , p_i) \in F_1 \times (Q_2 - F_2)  \, \cup \, (Q_1 -F_1) \times F_2 が存在したとき "no" を出力する。 \quad &\rightarrow end. \\
\rm(i\hspace{-.08em}v\hspace{-.06em}) \quad & ある a\in \Sigma に対して、 \\
& (q_i , a ,q_j) \in \delta_1 \quad (0 \le i , j \le N) \quad のとき \\
& (p_i , a ,p_j) \notin \delta_2 ならば、 "no" を出力する。 \quad &\rightarrow end. \\
\\
& 以上、\rm(\hspace{.18em}i\hspace{.18em}) , \rm(\hspace{.08em}ii\hspace{.08em}) , \rm(i\hspace{-.08em}i\hspace{-.08em}i) , \rm(i\hspace{-.08em}v\hspace{-.06em}) のアルゴリズムを順に行った結果、"no"と出力されなかったとき、"yes"を出力する。 \quad \rightarrow end. 
\end{aligned}

さて、最後に、このアルゴリズムを用いることによる、L(M_1^{\prime}) = L(M_2^{\prime}) の判定の正当性を論じる。ここで、


\begin{aligned}
\rm(\hspace{.18em}i\hspace{.18em}) \quad & は 「|Q_1|=|Q_2|」 \\
\rm(\hspace{.08em}ii\hspace{.08em}) \quad & は 「 \forall i , j \, ; \quad q_i \neq q_j \Rightarrow p_i \neq p_j 」\\
\rm(i\hspace{-.08em}i\hspace{-.08em}i) \quad & は 「\forall i \, ; (q_i ,p_i) \in (Q_1 - F_1) \times (Q_2 - F_2) \, \cup \, F_1 \times F_2」\\
\rm(i\hspace{-.08em}v\hspace{-.06em}) \quad & は 「\forall i , j \, ; \quad (q_i , a ,q_j) \in \delta_1 \Rightarrow (p_i , a ,p_j) \in \delta_2」
\end{aligned}


についての条件だとそれぞれ解釈できる。

よって、「L(M_1^{\prime}) = L(M_2^{\prime}) \Leftrightarrow \rm(\hspace{.18em}i\hspace{.18em}) かつ \rm(\hspace{.08em}ii\hspace{.08em}) かつ \rm(i\hspace{-.08em}i\hspace{-.08em}i) かつ \rm(i\hspace{-.08em}v\hspace{-.06em})が成立」を示すことができれば、アルゴリズムの正当性を示したことになる。


\rm(\,I\,) \quad L(M_1^{\prime}) = L(M_2^{\prime}) \Rightarrow \rm(\hspace{.18em}i\hspace{.18em}) かつ \rm(\hspace{.08em}ii\hspace{.08em}) かつ \rm(i\hspace{-.08em}i\hspace{-.08em}i) かつ \rm(i\hspace{-.08em}v\hspace{-.06em})が成立

背理法により \rm(\,I\,) を示す。すなわち、L(M_1^{\prime}) = L(M_2^{\prime}) であって、\rm(\hspace{.18em}i\hspace{.18em}) 不成立または \rm(\hspace{.08em}ii\hspace{.08em}) 不成立または \rm(i\hspace{-.08em}i\hspace{-.08em}i) 不成立または \rm(i\hspace{-.08em}v\hspace{-.06em})不成立とする。

いま、条件\rm(i\hspace{-.08em}i\hspace{-.08em}i)の不成立より、ある (q_i , p_i) \in F_1 \times (Q_2 - F_2) \, \cup \, (Q_1 - F_1 ) \times F_2 が存在する。

i=0 のとき、「 \phi \in L(M_1^{\prime}) かつ \phi \notin L(M_2^{\prime})」 または 「 \phi \notin L(M_1^{\prime}) かつ \phi \in L(M_2^{\prime})」 より、矛盾。

i \neq 0 のとき、ある文字数 N+1 以下の記号列 x_i が存在して q_i = \delta_1^{\star} (q_0 , x_i) , p_i = \delta_2^{\star} (p_0 , x_i) より、\left( \delta_1^{\star} (q_0 , x_i) , \delta_2^{\star} (p_0 , x_i)\right) \in F_1 \times (Q_2 - F_2) \, \cup \, (Q_1 - F_1 ) \times F_2 となっている。

これは「x_i \in L(M_1^{\prime}) かつ x_i \notin L(M_2^{\prime})」 または 「x_i \notin L(M_1^{\prime}) かつ x_i \in L(M_2^{\prime})」 を表しているから、矛盾。


\rm(I\hspace{-.01em}I) \quad \rm(\hspace{.18em}i\hspace{.18em}) かつ \rm(\hspace{.08em}ii\hspace{.08em}) かつ \rm(i\hspace{-.08em}i\hspace{-.08em}i) かつ \rm(i\hspace{-.08em}v\hspace{-.06em})が成立  \Rightarrow L(M_1^{\prime}) = L(M_2^{\prime})

まず、前準備として、次を満たす写像 \varphi : Q_1 \rightarrow Q_2 を定義する。


\begin{aligned}
& q_i \in Q_1 (0 \le i \le N) \, について \\
& i=0 のとき、\varphi (q_i) = p_0 \\
& i \neq 0 のとき、|x_i| \le N \, , \, \delta_1^{\star} (q_0 , x_i) = q_i \, なる \, x_i \, が存在するため、 p_i = \delta_2^{\star} (p_0 , x_i) とし、\varphi (q_i) = p_i
\end{aligned}


いま、\rm(\hspace{.08em}ii\hspace{.08em}) の条件が成り立つので

0 \le \forall i \lt \forall j \le N \quad \varphi (q_i) \neq \varphi (q_j) が成立するので、\varphi単射

また、\rm(\hspace{.18em}i\hspace{.18em}) の条件が成り立つから、 |Q_1| = |Q_2| = N+1

ここで、次に示す定理 ( \bigstar ) より、\varphi全単射であると分かる。


定理 ( \bigstar )

AB が同数の元を含む有限集合のとき、A から B への写像 f について、全射であるということと、単射であるということとは同値である。

(証明)

一般に fA から B への単射ならば |f(A)| = |A| となる。したがって、|A| = |B| \lt \infty ならば f(A) = B となり、f全射になる。逆に A が有限集合で f単射でなければ |f(A)| \lt |A| となるので、 f全射にならない。


このとき、M_1^{\prime}M_2^{\prime} に同型であることを示す。

\rm(i\hspace{-.08em}i\hspace{-.08em}i) の条件が成り立つから q_i \in F_i \Rightarrow \varphi(q_i) \in F_2 \, , \, p_i \in F_2 \Rightarrow \varphi^{-1} (p_i) \in F_1

よって、\varphi (F_1) = F_2 である。

また、\rm(i\hspace{-.08em}v\hspace{-.06em}) の条件が成り立つから、

\forall i,j \quad (q_i , a , q_j) \in \delta_1 \Rightarrow \left( \, \varphi (q_i) ,a, \varphi (q_j) \, \right) \in \delta_2

すなわち、q_j = \delta_1 (q_i ,a) のとき \varphi全単射性により \varphi (q_j) = \varphi \left( \delta_1 (q_i ,a) \right) だが、\delta_2 (\varphi (q_i) ,a) = \varphi (q_j) が成り立つことにより、

\delta_2 (\varphi (q_i) ,a) = \varphi \left(\delta_1 (q_i ,a) \right) = \varphi (q_j)

したがって、M_1^{\prime}M_2^{\prime} に同型。このとき、 L(M_1^{\prime}) = L(M_2^{\prime})


以上より、題意は示された。