本シリーズでは、以下の本に沿って解説を書いている。
前回は、決定性有限オートマトンと非決定性有限オートマトンそれぞれで、認識できる言語に差がないことを証明した。
また、その中で非決定性有限オートマトンを決定性に書き換える方法も解説した。
それぞれメリット、デメリットがあるので、適宜使い分けよう。
以下がその記事だ。
さて、今回はまたしても新しいタイプの有限オートマトンが出てくる。
その名も、\(\varepsilon\)入力付き非決定性有限オートマトン。
さらに話が複雑になるが、前回までの内容とどこが違うかに気を付けながら進めていこう。
\(\varepsilon\)入力付き非決定性有限オートマトン
…いい加減名前が長いので、これ以降名前を呼ぶ際には省略形を使うことにしよう。
- dfa : 決定性有限オートマトン
- nfa : 非決定性有限オートマトン
- \(\varepsilon\)nfa : \(\varepsilon\)入力付き非決定性有限オートマトン
これ以降は、このように省略することとする。
というわけで、\(\varepsilon\)nfaの解説だ。
\(\varepsilon\)nfaとは、状態遷移の際に、何の入力なしでも遷移することを許容するようなnfaのこと。
どういうことか、先に状態遷移図を見てみよう。
このとき、状態遷移の様子を表にすると以下のような感じ。
| 現状態 | \(0\) | \(1\) | \(\varepsilon\) |
|---|---|---|---|
| \(s_0\) | \(\phi\) | \(\{s_1\}\) | \(\phi\) |
| \(s_1\) | \(\{s_3\}\) | \(\phi\) | \(\{s_2, s_4\}\) |
| \(s_2\) | \(\phi\) | \(\{s_0\}\) | \(\phi\) |
| \(s_3\) | \(\{s_0\}\) | \(\{s_0, s_4\}\) | \(\phi\) |
| \(s_4\) | \(\{s_2, s_3\}\) | \(\phi\) | \(\{s_0\}\) |
ちょっと、これまでと書き方を変えている。
一番左の列が現状態、一番上の行が読み込む入力で、それによる遷移先がそれぞれのマスだ。
例えば、現状態\(s_0\)で0を読み込むとその遷移先はないので\(\phi\)、1を読み込むと\(\{s_1\}\)に遷移する、という見方だ。
さて、一つ疑問に思う点があるかと思う。
これまで、どんな状態でも空列\(\varepsilon\)を読むと、その場にとどまっていた。
今回、それによる遷移が定義できるようになったということで、その遷移先が書かれているのは大丈夫。
しかし、自身に向かう遷移が定義されていないように見える。
これは、詳細は後で解説するが、結論を言ってしまうと別に問題はない。
さて、では実際に列を読み込んでみよう。
1110という列を読み込んでみる。
まず、初期状態は\(s_0\)、そこから1を読むと、\(s_1\)に遷移する。
ここまではいい。
次に1を読み込む…のだが、ここで二つの場合に分けて考えてみよう。
先に、そのまま\(s_1\)から遷移することを考えると、行先が定義されていないので\(\phi\)。
そして、ここで1を読み込む前に状態遷移を行うことを考える。
今、\(s_1\)から\(\varepsilon\)による遷移先が\(\{s_2, s_4\}\)と定義されている。
つまり、ここで勝手に\(s_2\)や\(s_4\)へ向かうことも可能なのだ。
で、\(s_2\)に向かったとして、そこから1を読むと今度は\(s_0\)に遷移。
\(s_4\)に向かったとすると、そこから1を読めば\(\phi\)だ。
ということで、これらの和集合を取って、\(\{s_0\}\)が現在いる可能性のある状態、ということになる。
まあ、今は一つしかないので、11の時点では\(s_0\)にいるよ、ということ。
このように、結局最後に和集合で考えるので、\(\varepsilon\)による遷移先が定義されていなくても大丈夫、ということだ。
言い換えると、定義はされていないが、\(\varepsilon\)による遷移先には必ず自身が該当する、という認識でもいいだろう。
ただ、これはあくまで定義しなくてもいい理由であり、定義されていない理由ではない。
その理由はまた後半で。
では、列読み込みの続きをやっていこう。
今、1110のうち11まで読み込んでいて、いる可能性のある状態の集合は\(\{s_0\}\)だ。
ここから、さらに10を読み込んでいこう。
1を読むと、上でやった通り\(s_1\)に遷移。
そこから0を読むと…まず\(\varepsilon\)遷移なしだと、\(s_3\)に向かう。
で、この時点で全部の列を読み終え、受理状態にいるので、1110が受理されることが分かった。
一応、\(\varepsilon\)遷移することも考えてみる。
\(s_2\)に遷移し、そこから0を読むと\(\phi\)。
\(s_4\)に遷移し、そこから0を読むと\(\{s_2, s_3\}\)。
よって、初期状態\(s_0\)から1110を読むと、最終的に\(\{s_2, s_3\}\)に遷移する、という感じだ。
こんな動作をするのが、\(\varepsilon\)nfaだ。
様相とステップ
これまでのdfaやnfaだと、状態遷移関数を使って列の遷移の様子を表していた。
しかし、この\(\varepsilon\)nfaでは、別の考え方を使って列の遷移を表現する。
やっていることは同じなのだが、状態遷移関数だと非常に複雑なので、それを簡略化するため…だろうか。
状態遷移関数による定義は、ネットで調べてもらえれば出てくるので、気になる人は調べてみよう。
さて、新しく、二つほど定義を導入していく。
まず、様相というもの。
様相とは、列と状態の組だ。
これは、列を読み込んでいる途中経過を表していると考えていいだろう。
例えば、現状態が\(s_1\)で、そこから残りの列110を読み込むという状況を、以下のように書き表す。
$$(110, s_1)$$
これについて、さらにステップという考え方も定義しよう。
ある二つの様相\(c_1 = (x_1, s_1)\)、\(c_2 = (x_2, s_2)\)について、以下の条件のいずれかを満たすとき、\(c_1\)から\(c_2\)へ1ステップで移れると定義する。
- \(x_1 = x_2\)かつ\(s_2 \in \delta(s_1, \varepsilon)\)
- \(a \in \Sigma\)として\(x_2 = ax_1\)かつ\(s_2 \in \delta(s_1, a)\)
一つ目は、\(s_1\)から\(s_2\)へ直接遷移するような\(\varepsilon\)遷移が存在すること、二つ目は単純に文字の遷移で\(s_1\)から\(s_2\)へ移れることを表している。
もっと簡単に言うと、両方とも状態遷移図において矢印一本で辿れることだ。
この1ステップを定義するために、\(\varepsilon\)による遷移先に自身が含まれていない、と考えられる。
もし含まれているとすると、まったく同じ様相にも1ステップかかると捉えられてしまうからだ。
さらに、\(c_1\)から\(c_2\)へ1ステップで移れるとき、二重矢印を使って以下のように表記する。
$$c_1 \Rightarrow c_2$$
では、このステップを複数に拡張しよう。
\(c_0 \Rightarrow c_1 \Rightarrow … \Rightarrow c_k\)のとき、\(c_1\)から\(c_k\)へは何ステップかで移れると定義し、矢印にアスタリスクをつけて以下のように表記する。
$$c_0 \overset{*}{\Rightarrow} c_k$$
ちなみに、\(c_0 = c_k\)のとき、0ステップで移れるとなり、これももちろん上の定義に含まれる。
さて、これを定義したことで、より形式的に列が受理されることの定義を書けるようになった。
ある列\(x \in \Sigma^*\)が受理されるとは、初期状態を\(s_0\)、受理状態のうち一つを\(s_F \in F\)とし、何ステップかで移れるような以下の様相が存在することである。
$$(x, s_0) \overset{*}{\Rightarrow} (\varepsilon, s_F)$$
ちょっと練習で、上で出した\(\varepsilon\)nfaに1110を入力したときの様子を、この様相を使って書いてみよう。
$$\begin{eqnarray}
& & (1110, s_0) \\
& \Rightarrow & (110, s_1) \\
& \Rightarrow & (110, s_2) \\
& \Rightarrow & (10, s_0) \\
& \Rightarrow & (0, s_1) \\
& \Rightarrow & (\varepsilon, s_3)
\end{eqnarray}$$
あるいは、
$$\begin{eqnarray}
& & (1110, s_0) \\
& \Rightarrow & (110, s_1) \\
& \Rightarrow & (110, s_2) \\
& \Rightarrow & (10, s_0) \\
& \Rightarrow & (0, s_1) \\
& \Rightarrow & (0, s_4) \\
& \Rightarrow & (\varepsilon, s_3)
\end{eqnarray}$$
このどちらかを提示することで、1110が受理されることを説明できる。
おわりに
今回は、\(\varepsilon\)nfaを解説した。
これまでとちょっと勝手が異なるが、様相やステップが表していることもしっかり理解しておこう。
さて、次回はこの\(\varepsilon\)nfaと、ただのnfaで同じ言語を認識できることを示してみようと思う。
以前やった、nfaとdfaのような感じだ。
これが分かると、dfa、nfa、\(\varepsilon\)nfaそれぞれで認識できる言語に差がないことが示せたことになる。
そして、さらにその次の話もしてしまうと、これらが正規表現と同じ言語を認識できることも示す。
つまり、これら4つは表記が異なるだけで、認識できる言語に差がないということだ。
証明はこれまで以上に複雑になりそうな気がしているが、一個一個確認しながら進めていこう。
コメント