本シリーズでは、以下の本に沿って解説を書いている。
前回は、有限オートマトンの同型について解説した。
これは上の参考書には載っていない内容だが、重要な概念だろうと思い、前回取り扱った。
また、同型かつ既約な有限オートマトンは全て同型になる、という定理も紹介した。
証明はともかく、何を言っているかは理解しておきたい。
以下がその記事だ。
さて、前回考えていた定理について、記事に追記した通り成り立たないことが分かってしまった。
あまりここに時間を割きすぎてもいけないので、悲しみを背負いつつ今回は先に進もう。
非決定性有限オートマトンという内容に進んでいく。
前回までより考え方が複雑になるので、注意しながら進んでいこう。
非決定性有限オートマトン
さて、これまで考えていた有限オートマトンは、実は決定性有限オートマトンという名前がついている。
どの状態に対しても、ある記号を入力した遷移先が一意に決定していたから、決定性有限オートマトンだ。
そこから言葉で考えると、非決定性有限オートマトンでは、ある記号を入力した遷移先が一意に決定しなくてもよい、ということになる。
実際その通りだ。
では、定義を。
非決定性有限オートマトンは、\(M = (K, \Sigma, \delta, s_0, F)\)という5つの組で与えられる。
ここは決定性有限オートマトンと同じで、それぞれが表しているものも同じ。
- \(K\) : 状態の集合
- \(\Sigma\) : 入力記号の集合
- \(\delta\) : 状態遷移関数
- \(s_0\) : 初期状態
- \(F\) : 受理状態の集合
状態遷移関数\(\delta\)の中身が決定性の時とは異なり、以下で定義される。
$$\delta : K \times \Sigma \rightarrow 2^K$$
遷移先が、\(2^K\)という集合になっている。
これはべき集合といって、\(K\)の任意の部分集合の集合を表している。
数式で書くと以下の通り。
$$2^K = \{K’ | K’ \subset K\}$$
例えば、\(K = \{s_0, s_1, s_2, s_3\}\)のとき、この\(2^K\)は以下16個の集合を要素として持つ集合だ。
$$\begin{eqnarray}
2^K = & \{ & \phi, \\
& & \{s_0\}, \{s_1\}, \{s_2\}, \{s_3\}, \\
& & \{s_0, s_1\}, \{s_0, s_2\}, \{s_0, s_3\}, \\
& & \{s_1, s_2\}, \{s_1, s_3\}, \{s_2, s_3\}, \\
& & \{s_0, s_1, s_2\}, \{s_0, s_1, s_3\}, \\
& & \{s_0, s_2, s_3\}, \{s_1, s_2, s_3\}, \\
& & \{s_0, s_1, s_2, s_3\} \\
& \} &
\end{eqnarray}$$
では、具体例を見ていこう。
参考書の例をお借りして、今回考える非決定性有限オートマトン\(M\)の状態遷移図は以下だ。
基本的な見方は決定性の時と全く同じだが、状態遷移の矢印が明らかに決定性の時とは異なることが分かるだろう。
決定性の場合には、全ての状態から、全ての記号に関する状態遷移の矢印が書かれており、さらにそれは必ず一つだけだった。
しかし、今回は状態\(s_0\)から記号1による遷移先が2本あるし、\(s_1\)以降では片方の記号による遷移先が書かれていない。
\(s_5\)にいたっては、そもそも矢印が一本も出ていない。
もちろん、書き忘れではない。
こういったものを許容するのが、非決定性有限オートマトンなのだ。
なお、後で具体的な遷移の様子をお見せするが、矢印が出ていない＝定義されていない、というわけではないので注意。
状態遷移関数の拡張
この状態遷移関数について、決定性の時と同じように、列に拡張したい。
まずは上の状態遷移図を使って、直感的に説明してみよう。
例えば、今初期状態である\(s_0\)にいて、そこから記号1を入力したとしよう。
このとき、記号1による矢印が二つ出ているので、その先である\(s_0\)、\(s_1\)どちらに遷移することも可能だ。
このような遷移を、\(\delta(s_0, 1) = \{s_0, s_1\}\)と表記する。
次に、今度は初期状態から10と入力されたとしよう。
上でやったように、まず1を受け取った時点で\(s_0, s_1\)のどちらかにいる。
そこから0を受け取ると、\(s_0\)だったら\(s_0\)へ、\(s_1\)だったら\(s_2\)へ遷移する。
つまり、列10による遷移先は\(\hat{\delta}(s_0, 10) = \{s_0, s_2\}\)だ。
ここまでは全部矢印があったので、特に問題はないと思う。
では、さらに後ろに0をつけて、列100を入力したとする。
10までは上と同じく、今\(s_0, s_2\)のいずれか。
ここで0を受け取ると、\(s_0\)は\(s_0\)へ遷移するのは問題ないが、\(s_2\)からは0による矢印は書かれていない。
このとき、状態遷移関数で書くと\(\delta(s_2, 0) = \phi\)であり、ここからはその記号で遷移できないことを表している。
つまり、\(s_0\)だけ先に進めるので、100を受け取った遷移先は\(\hat{\delta}(s_0, 100) = \{s_0\}\)となるのだ。
直感的には問題ないと思う。
では、これを数式で表現してみよう。
参考書では、以下のように記載されていた。
$$\begin{eqnarray}
\hat{\delta}(s, \varepsilon) & = & \{s\} \\
\hat{\delta}(s, xa) & = & \{q | p \in \hat{\delta}(s, x) \mbox{かつ} q \in \delta(p, a) \mbox{であるような} p \in K \mbox{が存在する}\}
\end{eqnarray}$$
もしこれで分かるのであれば全く問題ない。
…のだが、私がこれだとイマイチ理解できなかった。
そのため、以下の形に書き換えよう。
$$\begin{eqnarray}
\hat{\delta}(s, \varepsilon) & = & \{s\} \\
\hat{\delta}(s, xa) & = & \bigcup_{p \in \hat{\delta}(s, x)} \delta(p, a)
\end{eqnarray}$$
補足で、この二つ目について。
今、\(\hat{\delta}(s, x) = \{s_1, s_2, …, s_n\}\)だったとすると、以下のように書き換えが可能だ。
$$\bigcup_{p \in \{s_1, s_2, …, s_n\}} \delta(p, a) = \delta(s_1, a) \cup \delta(s_2, a) \cup … \cup \delta(s_n, a)$$
要するに、和集合の下に書かれている条件全てについて、右の集合を考え、それらを和集合にする。
ちょっと複雑なので、具体例で丁寧に計算していこう。
上で例示した非決定性有限オートマトン\(M\)で、初期状態から100を入力したとする。
この計算の様子を以下に示そう。
$$\begin{eqnarray}
\hat{\delta}(s_0, 100) & = & \bigcup_{p \in \hat{\delta}(s_0, 10)} \delta(p, 0) \\
\hat{\delta}(s_0, 10) & = & \bigcup_{p \in \hat{\delta}(s_0, 1)} \delta(p, 0) \\
\hat{\delta}(s_0, 1) & = & \bigcup_{p \in \hat{\delta}(s_0, \varepsilon)} \delta(p, 1) \\
\hat{\delta}(s_0, \varepsilon) & = & \{s_0\} \\
\hat{\delta}(s_0, 1) & = & \bigcup_{p \in \{s_0\}} \delta(p, 1) = \delta(s_0, 1) = \{s_0, s_1\} \\
\hat{\delta}(s_0, 10) & = & \bigcup_{p \in \{s_0, s_1\}} \delta(p, 0) = \delta(s_0, 0) \cup \delta(s_1, 0) = \{s_0\} \cup \{s_2\} = \{s_0, s_2\} \\
\hat{\delta}(s_0, 100) & = & \bigcup_{p \in \{s_0, s_2\}} \delta(p, 0) = \delta(s_0, 0) \cup \delta(s_2, 0) = \{s_0\} \cup \phi = \{s_0\}
\end{eqnarray}$$
やたら複雑そうなことをしているように見えるが、実際は上でやった直感的な説明を数式に変換しているだけ。
頑張って手を動かしながら理解していこう。
列を受理することの定義
定義の最後にこれを見よう。
列\(x \in \Sigma^*\)が非決定性有限オートマトン\(M\)で受理されるとは、以下の式を満たすことである。
$$\hat{\delta}(s_0, x) \cap F \not = \phi$$
要するに、どれでもいいので受理状態のうち最低でも一つに到達することができるなら、その列\(x\)は\(M\)で受理されるという。
そして、それを集めた集合\(L(M)\)が、\(M\)の認識する言語だ。
$$L(M) = \{x \in \Sigma^* | \hat{\delta}(s_0, x) \cap F \not = \phi\}$$
おわりに
今回は、非決定性有限オートマトンというものを解説した。
今回の内容ももちろんだが、今まで扱っていたのは決定性有限オートマトンである、ということも併せて覚えておいて欲しい。
さて、次回はこれら決定性、非決定性の有限オートマトンの書き換えと、言語の補集合を認識する非決定性有限オートマトンに進んでいこう。
次回解説するが、今回例に出した非決定性有限オートマトンを、決定性有限オートマトンに書き換えてみてほしい。
また、その補集合を認識するものにもチャレンジしてみよう。
実は、これらは一筋縄ではいかない。
条件など注意深く見ながら、やってみて欲しい。
2020/12/13追記
次回の内容を更新した。
上に書いた通り、決定性・非決定性の関係と、言語の補集合を認識する非決定性有限オートマトンだ。
だんだんと複雑になってきているので、少しずつ理解しながら進めていこう。
コメント