本シリーズでは、以下の本に沿って解説を書いている。
前回は、有限オートマトンの等価と、言語の補集合を認識する有限オートマトンを解説した。
等価は今回も使うので、不安なら復習しておこう。
以下がその記事だ。
さて、今回は…申し訳ないが、再度横道に逸れる。
前回の中で、二つの有限オートマトンが等しいとは、ということを考えた。
…調べたら、同型という名前がついていたので、改めて紹介しよう。
また、一つ興味深い定理も発見した。
その紹介と証明もやってみよう。
なお、今回の内容は参考書には載っていない。
そのため、できる限り丁寧に解説していこう。
ちなみに、今回は二本立てだ。
次回、この同型をどうやって判定するかを考えていきたい。
その際は今回の内容を使うので、しっかり理解しておこう。
2020/12/10追記
…判定を行うために考えていた定理に、反例が見つかってしまった。
そのため、すぐにやるのが難しくなってしまった。
申し訳ないが、ちょっと考え直すので、しばらくお待ちいただきたい。
同型な有限オートマトン
まずはこれから。
前回、等しいという名前で考えたものに、実は同型という名前がついていた。
改めて定義していこう。
入力記号の集合が等しい二つの有限オートマトン\(M_1 = (K_1, \Sigma, \delta_1, s_0, F_1)\)と\(M_2 = (K_2, \Sigma, \delta_2, t_0, F_2)\)が同型であるとは、以下の条件を満たす\(K_1\)から\(K_2\)への全単射\(f\)が存在することである。
- \(K_2 = \{f(s) | s \in K_1\}\)
- \(\delta_2(f(s), a) = f(\delta_1(s, a))\)
※\(s \in K_1, f(s) \in K_2, a \in \Sigma\) - \(t_0 = f(s_0)\)
- \(F_2 = \{f(s) | s \in F_1\}\)
言い方を変えると、これら二つの有限オートマトンの状態遷移図を書いて、片方の状態名をうまく変えればもう片方の状態遷移図に完全に一致するとき、この二つの有限オートマトンを同型と呼ぶ。
…さて、二つほど気になる部分がある。
そこを補足していこう。
補足1：状態遷移関数について
まずは、状態遷移関数に関する定義について。
本来であれば、ある状態\(s \in K_1\)から\(a \in \Sigma\)による遷移\(\delta_1(s, a)\)について、写像先でも同じ対応になっている、という条件のはずだ。
式で書くと以下の通り。
$$\delta_1(s, a) = s’ \Leftrightarrow \delta_2(f(s), a) = f(s’)$$
これを式①としておこう。
これが、なぜ上の定義の形(式②とする)で問題ないかを示していく。
ここでの証明方針は以下の通り。
- 式①を前提とし、式②が成り立つことを示す
- 式②を前提とし、式①が成り立つことを示す
- 式①の左を前提とし、式①の右が成り立つことを示す
- 式①の右を前提とし、式①の左が成り立つことを示す
では、順番に見ていこう。
まず式①ならば式②となることについて、式①の左側の内容を右の\(s’\)に代入しよう。
$$\delta_2(f(s), a) = f(s’) = f(\delta_1(s, a))$$
これは式②なので、成立だ。
次に、式②ならば式①となることについて、さらに二段階で示していく。
ここでの前提は、式②と式①の左側だ。
今度は、式②の\(\delta_1(s, a)\)に、式①の左の内容を代入していく。
$$\delta_2(f(s), a) = f(\delta_1(s, a)) = f(s’)$$
さっきと逆のことをしているだけなので、問題ないだろう。
最後、式②と式①の右側を前提として、式①の左側となることを示していこう。
今度は、式②の\(\delta_2(f(s), a)\)に、式①の右側の内容を代入する。
$$f(s’) = f(\delta_1(s, a))$$
さて、前提から\(f\)は全単射であったことを思い出そう。
全単射の定義から、同じ写像先になった場合、その写像元も同じになる。
そのため…
$$s’ = \delta_1(s, a)$$
が言えた。
以上から、示すべき全パターンを示せたので、この書き換えが問題ないことが証明できた。
補足2：受理状態について
これも補足しておこう。
こちらは、\(f\)による写像の前後で受理状態かどうかが一致していてほしい、というのが本来の内容。
式だと以下の通り。
$$s \in F_1 \Leftrightarrow f(s) \in F_2$$
これも、上の形\(F_2 = \{f(s) | s \in F_1\}\)に書き直せることを示しておこう。
こちらは、同値を繋げていく方針にする。
出発地点は、定義内の形にしよう。
まず、これは集合のイコールなので、以下の形に変形できる。
$$f(s) \in F_2 \Leftrightarrow f(s) \in \{f(s) | s \in F_1\}$$
ここで、\(f(s)\)が集合\(\{f(s) | s \in F_1\}\)に入るための条件は\(s \in F_1\)なので…
$$f(s) \in \{f(s) | s \in F_1\} \Leftrightarrow s \in F_1$$
この同値関係を繋げれば…
$$f(s) \in F_2 \Leftrightarrow s \in F_1$$
が示せた。
等価と同型の関係
さて、ちょっとこれを考えてみよう。
まず、二つの有限オートマトンが同型であれば、それらは等価でもある。
これは、状態遷移図が同じ形になっているので、その意味から考えれば明らかだろう。
…とはいえ、やはり証明は必要かと思うので、今回のオマケで示すことにする。
ここまではいいと思うのだが、ここからが注意だ。
二つの有限オートマトンが等価であったとしても、それらが同型とは限らない。
例えば、ある有限オートマトン\(M_1\)内に等価な2状態が存在し、それを縮小して別の有限オートマトン\(M_2\)を作ったとしよう。
このとき、以前やったように\(M_1\)と\(M_2\)は同じ言語を認識するので等価だ。
しかし、今状態数が異なっている。
ということは、全単射はどう頑張っても作れないので、同型ではない。
ちなみに、状態数が等しい、という条件だけでもまだ弱く、この条件で同型でない例は存在する。
2020/12/10追記
折角なので、成り立つと勘違いしていた内容もここで触れておこう。
二つの等価な有限オートマトン\(M_1\)、\(M_2\)で、\(s \equiv t\)となる\(s \in K_1, t \in K_2\)を考える。
このとき、\(|[s]| = |[t]|\)であれば、\(M_1\)と\(M_2\)は同型、というのが成り立っていてほしかった。
しかし、これにも反例が存在する。
同じ入力記号で、異なる言語を認識する(=等価でない)それぞれ既約な有限オートマトン\(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)\)を考える。
これらの中には、到達不可な状態は存在しないとしよう。
このとき、これらがともに既約であれば、これらは同型である。
何を言っているかというと、同じ言語を認識する最小の有限オートマトンは、必ず同じ形になる、ということだ。
非常に綺麗な定理だ。
では、これを証明するのだが、ちょっと方針を考えてみよう。
というのも、今同型を示したいのだが、そのためには定義を満たす全単射が作れることを示さなければいけない。
そこで、以下の3段階に分ける。
- 対応\(f\)を定義する
- 前提の元、この対応\(f\)が必ず全単射として作れることを示す
- この全単射\(f\)が同型の定義を満たすことを示す
こうすれば大丈夫だろう。
では、早速対応を定義…する前に、それに使う定義をしていく。
定義：二つの有限オートマトンにおける状態の等価
以前定義した状態の等価は、一つの有限オートマトン内の話だった。
これを、二つの有限オートマトンに拡張しよう。
入力記号の集合が等しい二つの有限オートマトン\(M_1\)、\(M_2\)に注目する。
状態\(s \in K_1, t \in K_2\)が等価である、というのを任意の列\(x \in \Sigma^*\)を使って以下の式で定義する。
$$\delta_1(s, x) \in F_1 \Leftrightarrow \delta_2(t, x) \in F_2$$
また、記法はそのまま\(s \equiv t\)としよう。
要するに、異なる有限オートマトンであったとしても、同じ列を読み込んだ際に受理状態かどうかが一致している関係を等価と呼ぶことにする。
これに関して、後で使える補題があるのでサクッと証明しておこう。
補題1：等価な状態の遷移先
入力記号の集合が等しい二つの有限オートマトンを\(M_1\)、\(M_2\)とする。
それぞれの状態\(s \in K_1, t \in K_2\)について、任意の列\(x \in \Sigma^*\)で以下が成り立つ。
$$s \equiv t \Rightarrow \delta_1(s, x) \equiv \delta_2(t, x)$$
等価な状態同士に対し、同じ列で遷移した先も等価だ、というもの。
本当は記号でやるべきだが、任意の列の中には記号も含まれているので、こちらだけ示せば記号でも成り立つのは明らかだ。
ということでさっさと証明してしまおう。
まず、前提から\(s \equiv t\)なので、これらから任意の列\(xy\)(\(x, y \in \Sigma^*\))で遷移した先が受理状態かどうかは一致している。
$$\delta_1(s, xy) \in F_1 \Leftrightarrow \delta_2(t, xy) \in F$$
ここで、状態遷移関数を分解する。
$$\begin{eqnarray}
\delta_1(s, xy) & = & \delta_1(\delta_1(s, x), y) \\
\delta_2(t, xy) & = & \delta_2(\delta_2(t, x), y)
\end{eqnarray}$$
上の式を、このイコールで書き替える。
$$\delta_1(\delta_1(s, x), y) \in F_1 \Leftrightarrow \delta_2(\delta_2(t, x), y) \in F_2$$
ちょっと分かりづらいかもしれないが、これは等価の定義の形になっている。
どれが等価かというと…
$$\delta_1(s, x) \equiv \delta_2(t, x)$$
この二つだ。
よって、証明完了だ。
ステップ1：対応の定義
ちょっと間が空いたが、対応を定義していこう。
今回、上で定義した等価な状態同士をこの対応で結ぶ。
つまり、\(f(s) = \{t \in K_2 | s \equiv t\}\)だ。
なお、\(|f(s)| = 1\)、つまり\(f\)が写像として定義可能であれば、その要素をそのまま書くこととする。
例えば、\(f(s) = \{t\}\)なら、\(f(s) = t\)と表記する、ということ。
さて、これが本当に全単射として定義できるのだろうか。
ステップ2で、それを見ていこう。
ステップ2：全単射の証明
これを示すために、何を言えればいいかから確認しておく。
全単射は全射かつ単射である写像なので、以下3つが言えればいい。
- \(f\)は写像である
- \(f\)は全射である
- \(f\)は単射である
もうちょっと具体的にしてみよう。
- 任意の\(s \in K_1\)について、\(|f(s)| = 1\)である
- 任意の\(t \in K_2\)について、\(f(s) = t\)となる\(s \in K_1\)が存在する
- 任意の\(s_1, s_2 \in K_1\)について、\(f(s_1) = f(s_2)\)であれば\(s_1 = s_2\)である
これが分からない場合は、対応や写像、全単射の定義を確認してほしい。
ということで、この三つを証明していこう。
写像であることの証明
まず、任意の\(s \in K_1\)について、\(|f(s)| = 1\)であることを示す。
これを言うためには、任意の\(s \in K_1\)について、\(s \equiv t\)となる\(t \in K_2\)がただ一つ存在することを言えばいい。
ということで、さらに二つに分けよう。
- 任意の\(s \in K_1\)について、\(s \equiv t\)となる\(t \in K_2\)が存在する
- 任意の\(s \in K_1\)と\(t, t’ \in K_2\)について、\(s \equiv t\)かつ\(s \equiv t’\)であれば\(t = t’\)である
とりあえず存在するということと、それがただ一つであるという二つに分けた。
では、一つ目から。
前提から\(M_1\)と\(M_2\)は等価なので、任意の列\(x \in \Sigma^*\)について、それを受理するかどうかは一致している。
$$\delta_1(s_0, x) \in F \Leftrightarrow \delta_2(t_0, x) \in F_2$$
等価の定義から、とりあえず初期状態同士は等価である、つまり\(s_0 \equiv t_0\)であることが分かった。
次に、今\(M_1\)には到達不可な状態は存在しないので、任意の状態\(s \in K_1\)に到達できる列\(x \in \Sigma^*\)が存在する。
\(K_1 = \{s_0, s_1, …, s_n\}\)とし、状態\(s_i \in K_1\)に到達する列の一つを\(x_i \in \Sigma^*\)としておこう。
このとき、\(\delta_1(s_0, x_i) = s_i\)という関係が成り立っている。
この列\(x_i\)を今度は\(M_2\)に入力すると、状態\(\delta_2(t_0, x_i)\)に遷移する。
そして、上で示した通り\(s_0 \equiv t_0\)なので、補題1から…
$$\delta_1(s_0, x_i) \equiv \delta_2(t_0, x_i)$$
が成り立っている。
つまり、\(s_i \equiv \delta_2(t_0, x_i)\)、ということで等価な状態が存在する。
これで前半はOK、後半に進もう。
今、\(s \equiv t\)、\(s \equiv t’\)が分かっている。
このとき、まずは\(t \equiv t’\)が分かる。
そして、前提で\(M_2\)は既約…つまり、異なる2状態同士はいずれも等価でない。
ということは、\(t \equiv t’\)となるのは\(t = t’\)しかあり得ない。
よって、こちらも正しい。
以上から、\(f\)は写像であると分かった。
上にも書いた通り、これ以降は\(f(s) = t\)のように、一つの要素を対応させる形で表記しよう。
全射であることの証明
次に、任意の\(t \in K_2\)について、\(f(s) = t\)となる\(s \in K_1\)が存在することを示そう。
上の証明の中で、\(s_0 \equiv t_0\)は分かっているので、ここはOK。
次に、今度は任意の\(t \in K_2\)へ到達するような列を考える。
\(K_2 = \{t_0, t_1, …, t_m\}\)とし、\(t_i \in K_2\)に到達する列の一つを\(x_i \in \Sigma^*\)としよう。
つまり、\(t_i = \delta_2(t_0, x_i)\)だ。
今度は、これを\(M_1\)に入力すると、\(\delta_1(s_0, x_i)\)という状態に到達する。
\(s_0 \equiv t_0\)と補題1から、\(t_i \equiv \delta_1(s_0, x_i)\)なので、\(f(\delta_1(s_0, x_i)) = t_i\)より成立だ。
これで、\(f\)は全射だ。
単射であることの証明
今度は、任意の\(s_1, s_2 \in K_1\)について、\(f(s_1) = f(s_2)\)であれば\(s_1 = s_2\)であることを示していく。
ちょっと証明する内容を書き換えよう。
\(f(s_1) = f(s_2) = t\)として、\(s_1 \equiv t\)かつ\(s_2 \equiv t\)ならば\(s_1 = s_2\)を示す。
…上で似たようなことをしたのを覚えているだろうか。
その時と全く同じ方針でいける。
まず、\(s_1 \equiv t\)かつ\(s_2 \equiv t\)なので、\(s_1 \equiv s_2\)だ。
そして、\(M_1\)は既約、どの二つも等価でないので、\(s_1 = s_2\)となる。
よって成立、\(f\)は単射でもある。
以上から、今回定義した対応\(f\)は全単射であることが示せた。
ステップ3：同型の定義
さあ、最後のステップだ。
上で確認した全単射\(f\)が、同型の定義を満たしているかを確認していこう。
なお、ここでは以下三つの前提を使うことにしよう。
- \(M_1\)と\(M_2\)が等価である
- \(M_1\)、\(M_2\)には到達不可な状態が含まれていない
- 上の全単射\(f\)が定義できている
何を言いたいかというと、既約という条件はここでは使わない、ということ。
なぜこれを明記したかというと、次回の内容で使いたいからだ。
今は深くは気にしなくてもいい。
ということで、証明に入ろう。
入力記号の集合は\(M_1\)、\(M_2\)が等価であることから等しいことが分かっているので、そこはOK。
残りの4要素を見ていく。
まず、状態の集合…は、今\(f\)が全単射だと分かったので、明らかに\(K_2 = \{f(s) | s \in K_1\}\)だと言える。
もし余分な要素が\(K_2\)に含まれていれば、全射ではなくなってしまう。
逆に、\(K_2\)に必要な要素が足りていなければ、今度はそもそも\(f\)が写像ではなくなってしまうか、写像だったとしても単射ではなくなる。
ということで問題ない。
次に、一つ飛ばして初期状態も、上の証明の中で\(f(s_0) = t_0\)と分かっているので問題ないだろう。
では、飛ばした状態遷移関数を見てみよう。
定義は、以下のような関係が成り立っていることだった。
$$\delta_2(f(s), a) = f(\delta_1(s, a))$$
まず、全単射\(f\)の定義から、\(s \equiv f(s)\)が分かる。
次に、任意の記号\(a \in \Sigma\)に対し、補題1から以下が言える。
$$\delta_1(s, a) \equiv \delta_2(f(s), a)$$
全単射\(f\)の定義を使って書き直すと…
$$f(\delta_1(s, a)) = \delta_2(f(s), a)$$
ということで、成立だ。
では最後に、受理状態について、\(F_2 = \{f(s) | s \in F_1\}\)が成り立っていることを示そう。
補足2の内容を使って、\(s \in F_1 \Leftrightarrow f(s) \in F_2\)を示すことにする。
まず右向き矢印、\(s \in F_1 \Rightarrow f(s) \in F_2\)から見ていこう。
\(M_1\)には到達不可な状態が存在しないので、\(s = \delta_1(s_0, x)\)となる列\(x \in \Sigma^*\)が存在する。
このとき、初期状態から受理状態に遷移しているので、列\(x\)は\(M_1\)で受理される。
\(M_1\)、\(M_2\)は等価なので、この列\(x\)は\(M_2\)でも受理される。
つまり、\(t = \delta_2(t_0, x)\)となる状態\(t\)も受理状態に含まれている。
さらに、上で\(s_0 \equiv t_0\)が言えており、補題1から\(\delta_1(s_0, x) \equiv \delta_2(t_0, x)\)。
イコールを置き換えて\(s \equiv t\)、全単射\(f\)の定義から\(t = f(s)\)まで分かった。
で、\(t \in F_2\)なので、\(f(s) \in F_2\)、これが示したかったことなので成立だ。
ラスト、左向き矢印である\(f(s) \in F_2 \Rightarrow s \in F_1\)を示そう。
まず、\(f(s) = t\)と置いておこう。
\(M_2\)には到達不可な状態が存在しないので、\(t = \delta_2(t_0, x)\)となる列\(x \in \Sigma^*\)が存在する。
このとき、初期状態から受理状態に遷移しているので、列\(x\)は\(M_2\)で受理される。
\(M_1\)、\(M_2\)は等価なので、列\(x\)は\(M_1\)でも受理される。
つまり、\(s’ = \delta_1(s_0, x)\)となる状態\(s’\)も受理状態に含まれている。
\(s_0 \equiv t_0\)、補題1から\(\delta_1(s_0, x) \equiv \delta_2(t_0, x)\)。
イコールを書き換えて\(s’ \equiv t\)、全単射の定義から\(t = f(s’)\)。
ここまで、ほぼ上と同じ議論を進めてきた。
さて、ここで最初に\(f(s) = t\)と置いていたので、\(f(s) = f(s’)\)となっている。
\(f\)は単射なので、\(s = s’\)だ。
\(s’ \in F_1\)だったので、\(s \in F_1\)、ということで、こちら側も示せた。
以上の内容から、全単射\(f\)は同型の定義を満たしている。
よって、\(M_1\)と\(M_2\)が同型であることが示せた。
おわりに
今回は、有限オートマトンの同型について解説した。
ちょっと証明が分かりづらいかもしれないが、適宜必要な情報を調べながら進めてもらいたい。
なお、今回やった定理は他でも紹介されていたが、証明は自分で考えているので、もっといい方法があるかもしれない…
さて、今回の内容を使えば、とりあえず既約になっている有限オートマトンについては同型判定ができるようになった。
しかし、既約でない場合でも、同型となるパターンはある。
最終的にはプログラムで判定したい。
そこで、より一般的な内容で同型となる定理を考えたので、それを次回紹介しよう。
そして、それを使ってプログラムを組む際のアルゴリズムまで考えてみる。
恐らく、次回はより複雑になるので、今回の内容を理解してから進むようにしよう。
2020/12/10追記
冒頭に書いた通り、考えていたものに反例が見つかってしまったので、ちょっとパスさせてもらいたい…
次回は予定を変更して、ようやく次の単元である非決定性有限オートマトンに進んでいこう。
…もし同型に関する必要十分条件を知っている方がいらっしゃったら、助言を頂けると幸いだ。
2020/12/11追記
次回の内容を更新した。
次の単元に進んで、非決定性有限オートマトンというものを解説している。
これまでの内容が基礎にはなっているが、言っていることはだいぶ変わるので、何が違うかに意識して見るといいかもしれない。
オマケ：同型なら等価の証明
オマケで、これを証明してみよう。
二つの有限オートマトン\(M_1, M_2\)が同型なら等価だ、という内容。
本文中に書いたように、状態遷移図で見れば明らかにこれは成り立っているように思える。
しかし、今数式で同型を定義したので、それを使って証明できる。
さて、先に同型と等価の定義を再確認しておこう。
まず、二つの有限オートマトンが同型であるとは、以下の条件を満たす全単射\(f\)が存在することだった。
- \(K_2 = \{f(s) | s \in K_1\}\)
- \(\delta_2(f(s), a) = f(\delta_1(s, a))\)
※\(s \in K_1, f(s) \in K_2, a \in \Sigma\) - \(t_0 = f(s_0)\)
- \(F_2 = \{f(s) | s \in F_1\}\)
そして、二つの有限オートマトンが等価であるとは、任意の列\(x \in \Sigma^*\)について、それが受理されるかどうかが一致していることだった。
$$\delta_1(s_0, x) \in F_1 \Leftrightarrow \delta_2(t_0, x) \in F_2$$
これを示す前に、状態遷移関数の定義を拡張したい。
定義では、記号に対してしか定義していない。
これを、列でも使えるように拡張しよう。
示したいのは、任意の列\(x \in \Sigma^*\)に対して、以下が成り立っていること。
$$\delta_2(f(s), x) = f(\delta_1(s, x))$$
列\(x\)の長さに関する帰納法を使う。
まず、\(|x| = 0\)…つまり\(x = \varepsilon\)の時。
左辺は\(\delta_2(f(s), \varepsilon) = f(s)\)。
右辺は\(\delta_1(s, \varepsilon) = s\)より\(f(\delta_1(s, \varepsilon)) = f(s)\)。
よって成立。
次に、\(|x| = n\)で成り立っているとし、前に記号\(a \in \Sigma\)をつけ足して列\(ax\)で成り立つかを見ていく。
左辺から出発して、右辺の形に持っていこう。
$$\begin{eqnarray}
\delta_2(f(s), ax) & = & \delta_2(\delta_2(f(s), a), x) \\
& = & \delta_2(f(\delta_1(s, a)), x) \\
& = & f(\delta_1(\delta_1(s, a), x)) \\
& = & f(\delta_1(s, ax))
\end{eqnarray}$$
ということで成立だ。
では本題に戻って右向き、\(\delta_1(s_0, x) \in F_1 \Rightarrow \delta_2(t_0, x) \in F_2\)から示していこう。
\(F_2\)の定義から、\(f(\delta_1(s_0, x)) \in F_2\)が分かる。
今示した内容から、\(f(\delta_1(s_0, x)) = \delta_2(f(s_0), x)\)だ。
そして、定義から\(f(s_0) = t_0\)。
これを代入すると\(\delta_2(t_0, x) \in F_2\)なので、こちらはOK。
逆向き、\(\delta_2(t_0, x) \in F_2 \Rightarrow \delta_1(s_0, x) \in F_1\)…先に言ってしまうと、今やったことを逆方向に進んでいくだけだ。
定義から\(t_0 = f(s_0)\)なので、\(\delta_2(f(s_0), x) \in F_2\)。
上で示した内容から、\(\delta_2(f(s_0), x) = f(\delta_1(s_0, x)) \in F_2\)。
\(F_2\)の定義から、\(\delta_1(s_0, x) \in F_1\)が言えた。
以上で証明完了だ。
コメント