本シリーズでは、以下の本に沿って解説を書いている。
前回は番外編ということで、有限オートマトンを表現するプログラムを作成した。
ちょっと長い記事だが、気になる人は見てみよう。
それまでは何をしていたかというと、有限オートマトンについて解説を行っていた。
今回も、その内容に戻ってくるので、不安な方は先に復習をしておいてもらいたい。
有限オートマトンの定義は以下の記事。
そして、直積オートマトンと状態の等価性については以下の記事だ。
今回、次の内容である非決定性有限オートマトンに進もう…と思ったのだが。
追加で二つほど解説したいことがあるので、先にそちらを解説する。
内容は、等価な有限オートマトンと、言語の補集合を認識する有限オートマトンだ。
前者は、実は上に載せた参考書には載っていない。
しかし、知っておいた方がいい概念ではあるので、解説しておこう。
後者は非常にカンタンなので、サクッと進めたい。
有限オートマトンの等価性
まずはこちらを見ていこう。
軽く復習で、以前やった状態の等価性を再確認してみる。
有限オートマトン\(M = (K, \Sigma, \delta, s_0, F)\)内の二つの状態\(s_i, s_j \in K\)が等価であるというのは、任意の列\(x \in \Sigma^*\)に対し、以下が成り立っていることだった。
$$\delta(s_i, x) \in F \Leftrightarrow \delta(s_j, x) \in F$$
日本語で書くと、どんな列を読み込んでも、それによる遷移先が受理状態に含まれるかどうかが一致していれば、その出発点の二つの状態は等価である。
これが、状態に関する等価の定義だ。
では、有限オートマトンの等価を見てみよう。
入力記号の集合が等しい二つの有限オートマトン\(M_1 = (K_1, \Sigma, \delta_1, s_0, F_1)\)、\(M_2 = (K_2, \Sigma, \delta_2, t_0, F_2)\)が等価であるというのは、以下が成り立っていることを言う。
$$L(M_1) = L(M_2)$$
要するに、それらによって認識される言語が全く同じであれば、その二つの有限オートマトンは等価だ。
これを言い換えると、任意の列\(x \in \Sigma^*\)に対し、以下が成り立っている。
$$x \in L(M_1) \Leftrightarrow x \in L(M_2)$$
もう一つ言い換えてみよう。
同じく任意の列を\(x \in \Sigma^*\)とし、以下が成り立っている。
$$\delta_1(s_0, x) \in F_1 \Leftrightarrow \delta_2(t_0, x) \in F_2$$
任意の列\(x\)が受理されるかどうかが一致している、という関係であればいいのだ。
この形にすれば、状態の等価性と非常に似ているので、同じ等価という言葉が使われているのが自然に感じるだろう。
さて、今これをプログラムで判定したいとしよう。
上の定義によると、全ての列に対してそれが受理されるかどうかを調べる必要がある。
しかし、それでは調査対象が無限に存在してしまうので、調べ切ることなど不可能。
では、どのように判定すればいいのか。
…もちろん、アルゴリズムが用意されている。
それに使える定理を一つ紹介しよう。
有限オートマトンの等価性と直積オートマトン
入力記号の集合が等しい二つの有限オートマトンを\(M_1 = (K_1, \Sigma, \delta_1, s_0, F_1)\)、\(M_2 = (K_2, \Sigma, \delta_2, t_0, F_2)\)とする。
これらには、初期状態から到達できない状態は含まれていないとする。
もし含まれていたとしたら、それを取り除いてあげればいい。
また、この二つの直積オートマトンを\(M = (K, \Sigma, \delta, (s_0, t_0), F)\)とする。
この\(M\)についても、すでに到達不可な状態は取り除かれているとしよう。
このとき、\(M_1\)と\(M_2\)が等価であることと、直積オートマトン内の全ての状態\((s, t) \in K\)に対し以下が成り立っていることが同値である。
$$s \in F_1 \Leftrightarrow t \in F_2$$
では、これを証明していく。
まずは、\(M_1\)と\(M_2\)が等価なら、\(M\)内の全ての状態で式が成り立っていることを示す。
\(M_1\)と\(M_2\)に対し、初期状態から任意の列\(x \in \Sigma^*\)で遷移させる。
それぞれの遷移先を、\(s\)、\(t\)と置いておこう。
$$\begin{eqnarray}
s & = & \delta_1(s_0, x) \\
t & = & \delta_2(t_0, x)
\end{eqnarray}$$
この二つを組にして、直積オートマトンの状態遷移関数の定義を使って変形する。
$$(s, t) = (\delta_1(s_0, x), \delta_2(t_0, x)) = \delta((s_0, t_0), x)$$
直積オートマトンの定義から、状態\((s, t)\)に到達できるので、\((s, t) \in K\)だ。
\(x\)は任意の列なので、これを変えていけば全ての\(K\)内の状態をこれで作り出すことができる。
前提から\(s = \delta_1(s_0, x) \in F_1 \Leftrightarrow t = \delta_2(t_0, x) \in F_2\)なので、成立だ。
次に反対方向、\(M\)内の全ての状態で式が成り立っているなら、\(M_1\)と\(M_2\)が等価であることを示していく。
先に、\(M_1, M_2\)には到達不可な状態は含まれていないので、\(M\)内の状態の組には必ず全ての\(K_1, K_2\)の要素が存在することを覚えておこう。
今度は、\(M\)に対して任意の列\(x \in \Sigma^*\)で初期状態から遷移させる。
その遷移後の状態を\((s, t)\)としておこう。
$$(s, t) = \delta((s_0, t_0), x)$$
状態遷移関数の定義で、右側を変形する。
$$\delta((s_0, t_0), x) = (\delta_1(s_0, x), \delta_2(t_0, x))$$
ここから、\(s, t\)は以下のように書き直すことができる。
$$\begin{eqnarray}
s & = & \delta_1(s_0, x) \\
t & = & \delta_2(t_0, x)
\end{eqnarray}$$
そして、前提から\(\delta_1(s_0, x) = s \in F_1 \Leftrightarrow \delta_2(t_0, x) = t \in F_2\)だ。
上で書いたように、\(M\)の状態\((s, t)\)の取り方を変えれば、全ての\(K_1\)、\(K_2\)の要素に対してこれを言うことができる。
よって、\(M_1\)、\(M_2\)の全ての状態に対して、上の式が成り立つ。
これは、有限オートマトンの等価の定義だ。
よって、\(M_1\)と\(M_2\)が等価であることが示せた。
以上で証明完了だ。
有限オートマトンの等価判定アルゴリズム
上の定理を使えば、二つの有限オートマトン\(M_1\)と\(M_2\)が等価であるかどうかが判定できるようになる。
アルゴリズムを以下に示そう。
- \(M_1\)と\(M_2\)の直積オートマトン\(M\)を作成する
- \(M\)から到達不可な状態を取り除く
- \(M\)内の全ての状態\((s, t) \in K\)に対し、以下を実行する
- \(s \in F_1\)の判定結果と\(t \in F_2\)の判定結果が異なれば、\(M_1\)と\(M_2\)は非等価と出力し、処理を終了する
- \(M_1\)と\(M_2\)は等価と出力し、処理を終了する
これでOKだ。
具体的な操作はここでは解説しないので、よかったら手を動かしてみてほしい。
オマケ：有限オートマトンの等価
ちょっと、プログラムで組む際の参考として、独自に考えてみたいことがある。
先に書いておくが、ここの内容は一般的な内容ではなく、本シリーズ固有の内容として捉えて欲しい。
上では、二つの有限オートマトンで表現しているものが同じ、という内容で等価を解説した。
では、二つの有限オートマトン自体が等しいとはどういうことだろうか。
そこで考えてみた。
入力記号の集合が等しい二つの有限オートマトン\(M_1, M_2\)について、これらが等しいとは、片方の状態の名前をもう片方に合わせると、遷移のしかたや初期状態、受理状態の集合が一致すること、だろうか。
言葉で書くと分かりづらいので、数式にしてしまおう。
\(M_1 = (K_1, \Sigma, \delta_1, s_0, F_1)\)、\(M_2 = (K_2, \Sigma, \delta_2, t_0, F_2)\)として、全単射\(f : K_1 \rightarrow K_2\)を考える。
つまり、\(s \in K_1\)に対し、\(f(s) \in K_2\)となっている。
これを使って…
- \(K_2 = \{f(s) | s \in K_1\}\)
- \(\delta_2(f(s), a) = f(\delta_1(s, a))\)
※\(a \in \Sigma\) - \(t_0 = f(s_0)\)
- \(F_2 = \{f(s) | s \in F_1\}\)
となるような全単射\(f\)が存在すれば、等しいと言えるだろう。
もうちょっと分かりやすく書くと、二つの状態遷移図を書いてみる。
そして、うまく片方の状態を書き換えると、もう一つの状態遷移図と完全に一致するなら、その二つは等しい、ということだ。
そのとき、例えば\(s \in K_1\)を\(t \in K_2\)に書き換えたなら、\(f(s) = t\)となる。
なぜこれを考えたかというと、プログラムで組む際に、インスタンスが等しいことを判定するために必要だからだ。
具体的に書くと、前回作ったプログラムでequals()メソッドをオーバーライドしたい。
最初はそこに等価判定を入れようとしたのだが、等価では等しいというにはちょっと条件が弱く感じた。
もう一つ言うと、有限オートマトン縮小のテスト結果判定に使いたかった。
元と等価であるかどうかも判断材料にはなるが、それでは最小かどうかが判定できない。
なので、手で求めた最小形と同じかどうか、という判定にしたかったのだ。
…まあ、オマケなので深くは気にしないでほしい。
2020/12/07追記
調べたら、上の関係には同型という名前がついていた。
これと等価に関する定理も見つけたので、別記事で解説しよう。
それを公開したらここにもリンクを記載するので少しお待ちいただきたい。
2020/12/08追記
ようやく証明が終えられた。
以下の記事で解説しているので、気になる人は見てみよう。
言語\(L(M)\)の補集合を認識する有限オートマトン
次にこれを見てみよう。
ある有限オートマトン\(M = (K, \Sigma, \delta, s_0, F)\)で認識される言語は\(L(M)\)だ。
これに対し、\(L(M)\)の補集合となる言語\(\Sigma^* – L(M)\)を認識する有限オートマトンがどうなっているか、という問題。
書き方を変えて、\(\Sigma^* \setminus L(M)\)でもいい。
これ、非常に単純で、\(M\)と受理状態のみ異なる有限オートマトン\(M’ = (K, \Sigma, \delta, s_0, F’)\)を考える。
この受理状態\(F’\)は…
$$F’ = K \setminus F = \{s \in K | s \not \in F\}$$
としてあげれば完成だ。
要するに、元の有限オートマトンで受理状態かどうかを入れ替えてあげるだけで完成する。
証明も非常にシンプル。
ある列\(x \in \Sigma^*\)が\(M\)で認識される、つまり\(x \in L(M)\)のとき…
$$\delta(s_0, x) \in F$$
となっている。
この\(x\)を\(M’\)に入力すると…
$$\delta(s_0, x) \not \in F’$$
が言える。
逆に、\(x \not \in L(M)\)の時は\(\delta(s_0, x) \not \in F\)で、\(\delta(s_0, x) \in F’\)となっているので、これで成立だ。
なお、次回解説する非決定性有限オートマトンというものでは、この考え方は通用しないので注意しておこう。
おわりに
今回は、有限オートマトン同士の等価と、言語の補集合を認識する有限オートマトンについて解説した。
ちょっとオマケ的な立ち位置だが、いずれも理解はしておこう。
さて、次回はようやく次の単元である非決定性有限オートマトンに進む。
これまでの内容を理解しておかないと色々と難しいと思うので、しっかり復習してから進むようにしよう。
コメント