オートマトン・言語と計算理論「ε入力付き非決定性有限オートマトン」

本シリーズでは、以下の本に沿って解説を書いている。

オートマトン・言語と計算理論 (電子情報通信レクチャーシリーズ)
オートマトン・言語と計算理論 (電子情報通信レクチャーシリーズ)

前回は、決定性有限オートマトン非決定性有限オートマトンそれぞれで、認識できる言語に差がないことを証明した。

また、その中で非決定性有限オートマトンを決定性に書き換える方法も解説した。

それぞれメリット、デメリットがあるので、適宜使い分けよう。

以下がその記事だ。

さて、今回はまたしても新しいタイプの有限オートマトンが出てくる。

その名も、\(\varepsilon\)入力付き非決定性有限オートマトン

さらに話が複雑になるが、前回までの内容とどこが違うかに気を付けながら進めていこう。

スポンサーリンク

\(\varepsilon\)入力付き非決定性有限オートマトン

…いい加減名前が長いので、これ以降名前を呼ぶ際には省略形を使うことにしよう。

  • dfa : 決定性有限オートマトン
  • nfa : 非決定性有限オートマトン
  • \(\varepsilon\)nfa : \(\varepsilon\)入力付き非決定性有限オートマトン

これ以降は、このように省略することとする。

というわけで、\(\varepsilon\)nfaの解説だ。

\(\varepsilon\)nfaとは、状態遷移の際に、何の入力なしでも遷移することを許容するようなnfaのこと。

どういうことか、先に状態遷移図を見てみよう。

\(\varepsilon\)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つは表記が異なるだけで、認識できる言語に差がないということだ。

証明はこれまで以上に複雑になりそうな気がしているが、一個一個確認しながら進めていこう。

コメント

タイトルとURLをコピーしました