オートマトン・言語と計算理論「正規表現とnfaの関係」

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

https://amzn.to/3pISGtG

前回は、ある言語が正規表現で生成可能なら、それを認識するような$\varepsilon$nfaが存在することを示した。

こちら側はそこまで難しくなく、理解もしやすかったと思う。

以下がその記事だ。

さて、今回は反対側。

…なのだが、以前証明した内容を使って示す内容を少し変えさせてもらう。

nfaで認識される言語は、正規表現によって生成可能である、という定理を証明していこう。

dfa、nfa、$\varepsilon$nfaそれぞれで認識できる言語に差はなかったので、これを示せば結局この4つによって出来上がる言語に差がないことが示せる。

ちょっと、今回の内容は個人的に難易度が高いように思っている。

一個ずつ丁寧に進めていこう。

今回証明する定理
おわりに
1. オマケ：具体例が正しいことの証明

今回証明する定理

改めて、今回証明する定理を紹介しよう。

言語$L$がnfa$N$で認識されるならば、その言語$L$を生成する正規表現$R$が存在する。

まあ、前回の逆で、かつ$\varepsilon$nfaがnfaになったような感じ。

先に、証明の方針を。

今回も帰納法だが、基準となる数字はそのnfaに含まれる状態遷移の数だ。

分かりやすく言うと、状態遷移図を書いたときの、矢印の本数について帰納法を行う。

ただ、例えば一本の矢印に2つの記号が書かれているような場合、それは2本の矢印として扱う。

より定式的に書いてみよう。

この数を$n$とすると、以下の式で表すことができる。

$$n = \sum_{s \in K} \sum_{a \in \Sigma} |\delta(s, a)|$$

長旅になりそうだが、先に旅に必要な道具を用意しておこう。

定義：nfaの部分

あるnfa$N = (K, \Sigma, \delta, s_0, F)$について、そのうち1状態を$s \in K$、受理状態の部分集合を$V \subset F$とする。

このとき、nfa$(K, \Sigma, \delta, s, V)$を、$N(s, V)$と表記する。

言葉で説明すると、元のnfa$N$について、初期状態を$s_0$から$s$、受理状態の集合を$F$からその部分集合$V$に変更したようなnfaを、$N(s, V)$と定義した。

定義：nfaが認識する言語を生成する正規表現

あるnfa$N$について、それが認識する言語を生成するような正規表現が存在したとしよう。

今示したいことを仮定しているように見えるかもしれないが、あくまで存在したら、の話だ。

で、この正規表現を、$Reg(N)$と表記することにする。

ここまでは単に表記だけなので、そこまで困るようなことはないだろう。

初期段階

では、証明に入っていこう。

まず、状態遷移が無いようなnfaについて示していく。

今回注目するnfaを$N = (K, \Sigma, \delta, s_0, F)$として、それぞれ見ていこう。

どちらのタイプでも受理状態以外は共通で、状態は$\{s_0\}$、状態遷移関数は上に書いた通りだ。

一つ目、受理状態が$F = \phi$のとき。

この$N$が認識する言語は、$L = \phi$だ。

このとき、正規表現も$\phi$にしてあげれば問題ないので成立。

二つ目、受理状態が$F = \{s_0\}$のとき。

このときに$N$が認識する言語は$L = \{\varepsilon\}$、つまり空列のみを受理する形になる。

すると、正規表現は$\varepsilon$とすればいいので、これも成立。

これで、第一ステップは完了だ。

…ここまでは問題ないと思う。

ちなみに、今回状態を$\{s_0\}$のみ、受理状態は初期状態が入っているかどうかのみ着目していたが、それぞれ他の状態を含んでいても同じ議論ができることに注意しておこう。

帰納段階

次に、これを見ていこう。

今回注目しているnfa$N$について、状態遷移図における矢印の数がこの$N$未満であるようなnfaが認識する言語を生成する正規表現が存在すると仮定する。

この仮定の元、nfa$N$が認識する言語を生成する正規表現が存在することを示していく。

この中の2状態$s, s’$と記号$a$について、$s’ \in \delta(s, a)$としておこう。

このとき、今存在するとした$s$から$s’$に向かう記号$a$による遷移を削除したnfaを$M$とする。

状態遷移の数が$N$未満となったので、帰納法の仮定より$M$が認識する言語を表現する正規表現は存在する。

また、以下4つのnfaを用意しておこう。

$M(s_0, F)$
$M(s_0, \{s\})$
$M(s’, \{s\})$
$M(s’, F)$

それぞれのnfaが何を意味しているかを補足しておく。

一つ目の$M(s_0, F)$はそのまま$M$と同じもので、$N$においては受理する列のうち、$M$を作る時に削除された状態遷移を通らないような列を受理する。

二つ目の$M(s_0, \{s\})$は、初期状態から削除された状態遷移の出発点まで遷移するような列を受理。

三つ目の$M(s’, \{s\})$は、削除された状態遷移の到着点を初期状態として、そこから出発点に遷移する列を受理。

四つ目の$M(s’, F)$は、削除された状態遷移の到着点を初期状態として、そこから$N$の受理状態に遷移する列を受理する。

これらについては状態遷移の数が$M$と同じなので、仮定からこの4つそれぞれが認識する言語を生成するような正規表現も存在する。

で、これらを組み合わせて$Reg(N)$を作ろう。

先に結論を出してしまうと、以下の式になる。

$$Reg(N) = Reg \bigl( M (s_0, F) \bigr) + Reg \bigl( M (s_0, \{s\}) \bigr) \cdot \Bigl( a \cdot Reg \bigl( M ( s’, \{s\}) \bigr) \Bigr)^* \cdot a \cdot Reg \bigl( M ( s’, F) \bigr)$$

…非常に長いしややこしいので、別の文字を使って置き直そう。

正規表現$A$から$D$を以下のように置く。

$A = Reg \bigl( M(s_0, F) \bigr)$
$B = Reg \bigl( M(s_0, \{s\}) \bigr)$
$C = Reg \bigl( M(s’, \{s\}) \bigr)$
$D = Reg \bigl( M(s’, F) \bigr)$

これを使って書き直すと…

$$Reg(N) = A + B(aC)^*aD$$

ここまでシンプルになる。

さて、なぜこうなるのかを説明していこう。

まず、正規表現$A$から$D$が何を表しているかだが、以下の図を見て欲しい。

これは状態遷移図に見えるが、厳密には状態遷移図ではないので注意。

意味としては、初期状態$s_0$から受理状態の一つ$s_F$に向かうような列を、正規表現$A$で生成できる、というイメージ。

他の$B$から$D$も同様の考え方だ。

また、赤の矢印は$N$から$M$を作る時に削除した状態遷移。

これを見ながら、3つのパターンで見ていこう。

赤の遷移を通る回数について、0回、1回、2回以上というパターン分けをしていく。

まず0回、今削除された状態遷移を通らないような列について。

これは、$A$をそのまま使えばいいことが分かる。

次に、削除された状態遷移を1回通るような列について。

この状態遷移を分解すると、以下のようになる。

初期状態$s_0$から状態$s$に列で遷移
状態$s$から状態$s’$に記号$a$で遷移
状態$s’$から状態$s_F$に列で遷移

このうち、一つ目の列は正規表現$B$で、三つ目の列は正規表現$D$で生成可能。

その間に、一回記号$a$を読めばいいので、正規表現は$BaD$となる。

そして、削除された状態遷移を2回以上通るような列について。

これも状態遷移を分解してみよう。

初期状態$s_0$から状態$s$に列で遷移
状態$s$から状態$s’$に記号$a$で遷移
状態$s’$から状態$s$に列で遷移
状態$s$から状態$s’$に記号$a$で遷移
状態$s’$から状態$s$に列で遷移
…
状態$s$から状態$s’$に記号$a$で遷移
状態$s’$から状態$s_F$に列で遷移

最初と最後、記号による遷移の部分は上と同じ。

残る状態$s’$から状態$s$への遷移について、この遷移を行う列は正規表現$C$で生成可能だ。

つまり、この列全体を生成する正規表現を考えると…

$$BaCaC…aCaD$$

こんな形になっていることが分かる。

で、$aC$は複数回の繰り返しなので、アスタリスクを使って…

$$BaC(aC)^*aD$$

となることが分かる。

では、これらをまとめていこう。

今、以下3種類で生成される列全てを受理したい。

$A$
$BaD$
$BaC(aC)^*aD$

つまり、単純にプラスで結べばいい。

$$A + BaD + BaC(aC)^*aD$$

…のだが、二つ目と三つ目を注意深く見ると、$B$と$aD$の間に$aC$が0回以上繰り返されると捉えることができる。

それを反映させると…

$$A + B(aC)^*aD$$

ということで、上に示した形にすることができた。

これで、$N$で受理する列を正規表現で生成可能だと分かったので、成立。

帰納段階も成立すると分かったので、以上で定理が証明完了だ。

具体例

本当に？と思われる方が多いと思う。

何しろ、書いている私自身そう思っているくらいだ。

そこで、具体例として実際に上の方法で正規表現を作っていこう。

まず、基本パターンから一個進んだ状態について。

言い換えると、状態遷移図で初期状態から一つの矢印だけを持つようなnfaを見てみる。

状態遷移の出発点を初期状態に限定しているのは、そうしないと結局その状態遷移を通ることができず、帰納法の初期段階と同じ形として考えられるからだ。

これには、以下の6パターンが考えられる。

1状態、かつその状態は受理状態である
1状態、かつその状態は受理状態ではない
2状態、かつ初期状態が受理状態、他方も受理状態である
2状態、かつ初期状態が受理状態、他方は受理状態ではない
2状態、かつ初期状態が受理状態ではなく、他方は受理状態である
2状態、かつ初期状態が受理状態ではなく、他方も受理状態ではない

これで、実際に上の証明で登場した正規表現$A$から$D$を見て、そこから$Reg(N)$を作っていこう。

では一つ目から、状態遷移図は以下だ。

このとき、これが認識する言語$L(N)$は、記号$a$が0回以上繰り返される列のみを含む。

また、今回は$s_0 = s = s’$、かつ$F = \{s_0\}$となっているので、4つの正規表現はいずれも$Reg(M)$と共通だ。

その$M$は、基本形の二つ目と同じ形。

ということで、まず正規表現$A$から$D$はいずれも$\varepsilon$だ。

これを使って$Reg(N)$を作ると…

$$\begin{eqnarray}
Reg(N) & = & A + B(aC)^*aD \\
& = & \varepsilon + \varepsilon (a \varepsilon)^*a \varepsilon \\
& = & \varepsilon + a^*a \\
& = & a^*
\end{eqnarray}$$

となる。

これが生成する言語は、明らかに$a$が0回以上の列なので、$L(N)$と一致した。

次にパターン2、今度は$s_0$が受理状態ではなくなる。

このとき、どう頑張っても受理状態に遷移できない…というか受理状態自体存在しないので、$L(N) = \phi$だ。

そして、上と同じく$s_0 = s = s’$となっている。

ではそれぞれの正規表現を見てみよう。

$A = Reg \bigl( M(s_0, \phi) \bigr) = \phi$
$B = Reg \bigl( M(s_0, \{s_0\}) \bigr) = \varepsilon$
$C = Reg \bigl( M(s_0, \{s_0\}) \bigr) = \varepsilon$
$D = Reg \bigl( M(s_0, \phi) \bigr) = \phi$

こんな感じだ。

これで$Reg(N)$を作ると…

$$\begin{eqnarray}
Reg(N) & = & A + B(aC)^*aD \\
& = & \phi + \varepsilon (a \varepsilon)^*a \phi \\
& = & \phi + a^*a \phi \\
& = & \phi
\end{eqnarray}$$

一つ補足で、正規表現$\phi$は前後にどんな正規表現を$\cdot$で繋げても$\phi$になっていたことを思い出そう。

ということで、結局正規表現も$\phi$になったので、問題なさそうだ。

では、状態を二つに増やし、それぞれ見ていこう。

パターン3、2状態で初期状態が受理状態、他方も受理状態のもの。

この$N$が認識する言語は、記号$a$が0回、あるいは1回のものだ。

これで各正規表現を作ると以下の通り。

$A = Reg \bigl( M(s_0, \{s_0, s\}) \bigr) = \varepsilon$
$B = Reg \bigl( M(s_0, \{s_0\}) \bigr) = \varepsilon$
$C = Reg \bigl( M(s, \{s_0\}) \bigr) = \phi$
$D = Reg \bigl( M(s, \{s_0, s\}) \bigr) = \varepsilon$

これで、$Reg(N)$を作ろう。

$$\begin{eqnarray}
Reg(N) & = & A + B(aC)^*aD \\
& = & \varepsilon + \varepsilon (a \phi)^* a \varepsilon \\
& = & \varepsilon + \phi^* a \\
& = & \varepsilon + \varepsilon a \\
& = & \varepsilon + a
\end{eqnarray}$$

これで、空列あるいは記号$a$一つのみを生成する正規表現になったので、OKだ。

パターン4、2状態で受理状態は初期状態のみ。

これが受理する列は空列$\varepsilon$のみ。

では、正規表現を見ていこう。

$A = Reg \bigl( M(s_0, \{s_0\}) \bigr) = \varepsilon$
$B = Reg \bigl( M(s_0, \{s_0\}) \bigr) = \varepsilon$
$C = Reg \bigl( M(s, \{s_0\}) \bigr) = \phi$
$D = Reg \bigl( M(s, \{s_0\}) \bigr) = \phi$

これで$Reg(N)$を作ると…

$$\begin{eqnarray}
Reg(N) & = & A + B(aC)^*aD \\
& = & \varepsilon + \varepsilon (a \phi)^* a \phi \\
& = & \varepsilon + \phi \\
& = & \varepsilon
\end{eqnarray}$$

ということで、$L(N)$と一致。

パターン5、2状態で受理状態は遷移先のみ。

これが受理する言語は、$\{a\}$だ。

正規表現を作ってみる。

$A = Reg \bigl( M(s_0, \{s\}) \bigr) = \phi$
$B = Reg \bigl( M(s_0, \{s_0\}) \bigr) = \varepsilon$
$C = Reg \bigl( M(s, \{s_0\}) \bigr) = \phi$
$D = Reg \bigl( M(s, \{s\}) \bigr) = \varepsilon$

ここから$Reg(N)$を作る。

$$\begin{eqnarray}
Reg(N) & = & A + B(aC)^*aD \\
& = & \phi + \varepsilon (a \phi)^* a \varepsilon \\
& = & \phi + \phi^* a \\
& = & \varepsilon a \\
& = & a
\end{eqnarray}$$

ということでOK。

最後のパターン6、2状態で受理状態はなし。

これはどんな列を受け取っても受理状態に遷移できず、認識する言語は$L(N) = \phi$だ。

正規表現作成の様子は以下の通り。

$A = Reg \bigl( M(s_0, \phi) \bigr) = \phi$
$B = Reg \bigl( M(s_0, \{s_0\}) \bigr) = \varepsilon$
$C = Reg \bigl( M(s, \{s_0\}) \bigr) = \phi$
$D = Reg \bigl( M(s, \phi) \bigr) = \phi$

$$\begin{eqnarray}
Reg(N) & = & A + B(aC)^*aD \\
& = & \phi + \varepsilon (a \phi)^* a \phi \\
& = & \phi + \phi^* a \phi\\
& = & \phi + \phi \\
& = & \phi
\end{eqnarray}$$

ということで問題なし。

これで、基本パターンから一個進んだ状態は全てOKだ。

…さて、これらはまだ抽象的であまり実感が湧かないと思う。

そこで、最後にもう少し実用的なnfaで正規表現を作ってみよう。

変換元となるnfa$N$は以下にしてみる。

これは加算のみの数式を受理するようなnfaで、かつその数字を1に限定している。

また、空列は許容していない。

例えば、これが受理する列の例を挙げると…

$1, 11, 111, …$
$1 + 1, 11 + 11, 1 + 111, …$

などなど。

では、$N$から正規表現を作ってみよう。

まず、正規表現$A$から$D$は以下の通りであった。

$A = Reg \bigl( M(s_0, F) \bigr)$
$B = Reg \bigl( M(s_0, \{s\}) \bigr)$
$C = Reg \bigl( M(s’, \{s\}) \bigr)$
$D = Reg \bigl( M(s’, F) \bigr)$

これを使って、$Reg(N)$は以下のように表すことができた。

$$Reg(N) = A + B(aC)^*aD$$

ということで、まず一つの状態遷移を削除し、$M_1$を作ろう。

どれでもいいのだが、例えば$s_1$から記号1によって$s_1$に遷移する部分を削除する。

今後も同じように状態遷移を削除していくのだが、これを$s_1 \overset{1}{\rightarrow} s_1$と表記することにする。

この$M_1$の状態遷移図は以下だ。

で、必要な正規表現は4種類あるのだが、添え字を付けて$A_1$から$D_1$とし、それぞれの内訳を見ていこう。

$A_1 = Reg \bigl( M_1(s_0, \{s_1\}) \bigr) = Reg(M_1)$
$B_1 = Reg \bigl( M_1(s_0, \{s_1\}) \bigr) = Reg(M_1)$
$C_1 = Reg \bigl( M_1(s_1, \{s_1\}) \bigr)$
$D_1 = Reg \bigl( M_1(s_1, \{s_1\}) \bigr)$

こんな感じだ。

さて、$Reg(M_1)$と$Reg \bigl( M_1(s_1, \{s_1\}) \bigr)$が必要になった。

まずは$Reg(M_1)$から、さらに$M_1$の状態遷移を削除して$M_2$を作ろう。

今度は、$s_1 \overset{+}{\rightarrow} s_0$を削除してみる。

この$M_2$の状態遷移図は以下。

すると、$M_1$を作るために必要な正規表現$A_2$から$D_2$は…

$A_2 = Reg \bigl( M_2(s_0, \{s_1\}) \bigr) = Reg(M_2)$
$B_2 = Reg \bigl( M_2(s_0, \{s_1\}) \bigr) = Reg(M_2)$
$C_2 = Reg \bigl( M_2(s_0, \{s_1\}) \bigr) = Reg(M_2)$
$D_2 = Reg \bigl( M_2(s_0, \{s_1\}) \bigr) = Reg(M_2)$

このように、全て$Reg(M_2)$と一致する。

さて、本来であればここからさらに状態遷移を取り除くのだが、上のパターン5と同じなので、それと照らし合わせて$Reg(M_2) = 1$だと分かる。

ここから、$Reg(M_1)$を組み立てよう。

なお、記号$+$は正規表現としての$+$と区別するため、ダブルクォーテーションで囲っている。

$$\begin{eqnarray}
Reg(M_1) & = & A_2 + B_2(aC_2)^*aD_2 \\
& = & Reg(M_2) + Reg(M_2) (“+”Reg(M_2))^* “+”Reg(M_2) \\
& = & 1 + 1 (“+”1)^* “+”1 \\
& = & 1(“+”1)^*
\end{eqnarray}$$

こうなった。

ここでもう一つの$Reg \bigl( M_1(s_1, \{s_1\}) \bigr)$も作っていこう。

これを$M_3$とし、状態遷移図を出すと以下のような感じだ。

今度は、状態遷移$s_0 \overset{1}{\rightarrow} s_1$を削除して$M_4$を作る。

$M_4$の状態遷移図は以下だ。

では、正規表現$A_4$から$D_4$を作ろう。

$A_4 = Reg \bigl( M_4(s_1, \{s_1\}) \bigr) = Reg(M_4)$
$B_4 = Reg \bigl( M_4(s_1, \{s_0\}) \bigr)$
$C_4 = Reg \bigl( M_4(s_1, \{s_0\}) \bigr)$
$D_4 = Reg \bigl( M_4(s_1, \{s_1\}) \bigr) = Reg(M_4)$

さらに二つの正規表現$Reg(M_4)$と$Reg \bigl( M_4(s_1, \{s_0\}) \bigr)$が必要だ。

…なのだが、$M_4$は上のパターン4と同じ形なので、$Reg(M_4) = \varepsilon$と分かる。

また、$M_4(s_1, \{s_0\})$の状態遷移図を出すと以下の通り。

これは、上のパターン5と一緒だ。

ということで、$Reg \bigl( M_4(s_1, \{s_0\}) \bigr) = “+”$だ。

では、組み合わせて$Reg(M_3)$を作ろう。

先に$A_4$から$D_4$を具体的にしておく。

$A_4 = Reg(M_4) = \varepsilon$
$B_4 = Reg \bigl( M_4(s_1, \{s_0\}) \bigr) = “+”$
$C_4 = Reg \bigl( M_4(s_1, \{s_0\}) \bigr) = “+”$
$D_4 = Reg(M_4) = \varepsilon$

これを使って、$Reg(M_3)$を計算すると…

$$\begin{eqnarray}
Reg(M_3) & = & A_4 + B_4(aC_4)^*aD_4 \\
& = & \varepsilon + “+”(1 “+”)^*1\varepsilon \\
& = & \varepsilon + “+”(1 “+”)^*1
\end{eqnarray}$$

ここで止めてもいいのだが、これが生成する列を具体的に書くと…

$$\varepsilon, +1, +1+1, +1+1+1, …$$

このように、$+1$の0回以上の繰り返しとなるので、もう一つだけ変形しておこう。

$$\begin{eqnarray}
Reg(M_3) & = & \varepsilon + “+”(1 “+”)^*1 \\
& = & (“+”1)^*
\end{eqnarray}$$

さて、これでようやく大元が計算できるようになった。

今正規表現を求めたい$Reg(N)$に必要な$A_1$から$D_1$は以下の通り。

$A_1 = Reg(M_1) = 1(“+”1)^*$
$B_1 = Reg(M_1) = 1(“+”1)^* = A_1$
$C_1 = Reg(M_3) = (“+”1)^*$
$D_1 = Reg(M_3) = (“+”1)^* = C_1$

また、$N$から$M_1$を作る時に取り除いた状態遷移は$s_1 \overset{1}{\rightarrow} s_1$だったので、$a = 1$だ。

これらを使って$Reg(N)$を見てみると…

$$\begin{eqnarray}
Reg(N) & = & A_1 + B_1(aC_1)^*aD_1 \\
& = & A_1 + A_1(1C_1)^*1C_1 \\
& = & A_1(1C_1)^* \\
& = & 1(“+”1)^* \bigl( 1 (“+”1)^* \bigr)^*
\end{eqnarray}$$

これで作成完了だ。

…本当にこれでいいかは、今回のオマケで示すことにしよう。

おわりに

今回証明した内容により、dfa、nfa、$\varepsilon$nfa、正規表現はいずれも同じ言語を認識したり表現したりすることができるということが証明できた。

…証明は追い付けなくても、この内容はしっかり覚えておこう。

さて、これでどんな列でも表現できる…ならよかったのだが、実は限界がある。

次回は、そのあたりを解説していこう。

2021/1/21追記

次回の内容を更新した。

軽めの内容だが、とりあえず限界があるということだけ知っておいてもらえればいいだろう。

オマケ：具体例が正しいことの証明

さて、本編で後回しにしていた具体例が正しいことを証明しよう。

改めて、まずnfa$N$の状態遷移図は以下の通り。

そして、そこから生成した正規表現$Reg(N)$は以下の通り。

$$Reg(N) = 1(“+”1)^* \bigl( 1 (“+”1)^* \bigr)^*$$

これらが同じ言語を構成することを示したい。

ということで、以下の方針でやってみようと思う。

nfa$N$をdfaに変換する
正規表現を$\varepsilon$nfaに変換する
2で変換した$\varepsilon$nfaをnfaに変換する
3で変換したnfaをdfaに変換する
1と4で得られたdfaが等価であることを示す

具体例だからこそできるゴリ押しだ。

これまでの復習にもちょうどいい。

では、早速やっていこう。

ステップ1：nfa$N$をdfaに変換

まずこれだ。

nfaからdfaへの変換は、以下の記事で解説しているのでそちらをご覧いただきたい。

では、実際に変換していく。

これで作るdfaを$D_1 = (K_1, \{1, +\}, \delta_1, \{s_0\}, F_1)$としておく。

まず、状態は元のnfaの状態のべき集合なので以下の通り。

$$K_1 = \{\phi, \{s_0\}, \{s_1\}, \{s_0, s_1\}\}$$

次に状態遷移関数について、結論を表で出してしまおう。

現状態	$1$	$+$
$\phi$	$\phi$	$\phi$
$\{s_0\}$	$\{s_1\}$	$\phi$
$\{s_1\}$	$\{s_1\}$	$\{s_0\}$
$\{s_0, s_1\}$	$\{s_1\}$	$\{s_0\}$

状態遷移関数$\delta_1$内訳

この表から、状態$\{s_0, s_1\}$へはたどり着けないので、省いてしまおう。

最後に受理状態、今一つ状態を取り除いたので$F_1 = \{\{s_1\}\}$だけになる。

以上から、状態遷移図を書いてみた。

後の都合上、これを先に既約へ直しておきたい。

…のだが、これは任意の2状態が等価ではないので、すでに既約だ。

ステップ2：正規表現$Reg(N)$を$\varepsilon$nfaに変換

では、次に進もう。

今度は、正規表現を変換し続け、最終的にdfaまで持っていく。

大元になる正規表現を再掲しておこう。

$$Reg(N) = 1(“+”1)^* \bigl( 1 (“+”1)^* \bigr)^*$$

まずはここから$\varepsilon$nfaを作る。

この変換方法は以下の記事だ。

では、やっていこう。

元の正規表現を分解していく。

$R_1 = 1$、$R_2 = (“+”1)^*$、$R_3 = \bigl( 1 (“+”1)^* \bigr)^*$とし、$Reg(N) = R_1R_2R_3$。

次に、$R_4 = “+”1$として、$R_2 = R_4^*$。

そして、$R_5 = 1(“+”1)^*$として、$R_3 = R_5^*$。

この$R_5$について、$R_2$を使って$R_5 = 1R_2$と表せる。

では、細かい順に$\varepsilon$nfaを組み立てていこう。

状態の名前は最後に一括でつけたいので、一旦丸だけで表現している。

まず、$R_4$から。

次に、これを使って$R_2$。

さらにこれを使って、$R_5$。

そして、$R_3$。

一応、$R_1$も個別で作っておこう。

最後に、$R_1$、$R_2$、$R_3$を繋げて、$Reg(N)$。

状態にも名前をつけておいた。

…ちょっと状態数がえらいことになっているが、めげずに進んでいこう。

なお、これでできた$\varepsilon$nfaに、$E$という名前をつけておく。

ステップ3：$\varepsilon$nfa$E$をnfaに変換

今作った$E$を、nfaに変換していく。

この変換方法は以下の記事を参照してほしい。

では、変換していこう。

この変換後のnfaを、$N’$としておく。

まず、状態について。

各状態における、対応$S$を以下の表に表してみた。

状態$s$	対応$S(s)$
$t_0$	$\{t_0\}$
$t_1$	$\{t_1, t_2, t_5, t_6, t_8, t_{11}\}$
$t_2$	$\{t_2, t_5, t_6, t_8, t_{11}\}$
$t_3$	$\{t_3, t_4\}$
$t_4$	$\{t_4\}$
$t_5$	$\{t_2, t_5, t_6, t_8, t_{11}\}$
$t_6$	$\{t_6, t_8, t_{11}\}$
$t_7$	$\{t_7, t_8, t_{11}\}$
$t_8$	$\{t_8, t_{11}\}$
$t_9$	$\{t_9, t_{10}\}$
$t_{10}$	$\{t_{10}\}$
$t_{11}$	$\{t_6, t_8, t_{11}\}$

変換後のnfaの状態一覧

次に、状態遷移関数。

…ちょっと作るのが面倒だったが、なんとか頑張ってみた。

以下がその一覧だ。

なお、本来の状態は上の二つの組、例えば$t_0, \{t_0\}$といった形になるのだが、簡略化して左の要素のみを書いている。

現状態	$1$	$+$
$t_0$	$\{t_1\}$	$\phi$
$t_1$	$\{t_7\}$	$\{t_3, t_9\}$
$t_2$	$\{t_7\}$	$\{t_3, t_9\}$
$t_3$	$\{t_5\}$	$\phi$
$t_4$	$\{t_5\}$	$\phi$
$t_5$	$\{t_7\}$	$\{t_3\, t_9\}$
$t_6$	$\{t_7\}$	$\{t_9\}$
$t_7$	$\{t_7\}$	$\{t_9\}$
$t_8$	$\{t_7\}$	$\{t_9\}$
$t_9$	$\{t_{11}\}$	$\phi$
$t_{10}$	$\{t_{11}\}$	$\phi$
$t_{11}$	$\{t_7\}$	$\{t_9\}$

$E$の状態遷移関数内訳

こうなった。

さて、これを見ると到達不可な状態がいくつかある。

初期状態は$(t_0, S(t_0))$なので、そこから辿れるものだけ残そう。

結果だけ出すと、$t_0, t_1, t_3, t_5, t_7, t_9, t_{11}$が元になっている7個が残る。

最後、受理状態は上で省いたおかげで三つ残り、$t_1, t_7, t_{11}$が元となるものだ。

これらをもとに、$N’$の状態遷移図を書いてみよう。

なお、状態は今後のことも考えて、$(t_i, S(t_i))$を改めて$t_i$と置き換えている。

…一応状態数は減ってくれたものの、7状態。

次のdfaは最悪128状態となるので、ちょっと覚悟を決めつつ次に進んでいく。

ステップ4：nfa$N’$をdfaに変換

ここで、さっき$N$でやったようにdfaへ変換していく…のだが。

今書いたように、最悪の場合128状態となる。

流石に手作業でやるにはキツいので、初期状態だけ先に求め、状態遷移関数を作りながら必要な状態だけ抜き出してくる形にしよう。

というわけで、これで作るdfaを$D_2$とし、その初期状態を$\{t_0\}$とする。

ここから、頑張って作っていこう。

$\{t_0\}$に$1$を入力すると$\{t_1\}$、$+$を入力すると$\phi$。

今出てきた$\{t_1\}$に$1$を入力すると$\{t_7\}$、$+$を入力すると$\{t_3, t_9\}$。

こんな感じでどんどん続けていく。

表形式で進めていこう。

なお、上から順番に辿っている形で表記しており、新しい状態は赤字で示しておこう。

現状態	$1$	$+$
$\{t_0\}$	$\{t_1\}$	$\phi$
$\{t_1\}$	$\{t_7\}$	$\{t_3, t_9\}$
$\{t_7\}$	$\{t_7\}$	$\{t_9\}$
$\{t_3, t_9\}$	$\{t_5, t_{11}\}$	$\phi$
$\{t_9\}$	$\{t_{11}\}$	$\phi$
$\{t_5, t_{11}\}$	$\{t_7\}$	$\{t_3, t_9\}$
$\{t_{11}\}$	$\{t_7\}$	$\{t_9\}$
$\phi$	$\phi$	$\phi$

$D_2$の状態遷移関数内訳

なんと、たった8状態で収まってくれた。~~助かった…~~

ということで、状態の集合は上の表における現状態の列のもの。

受理状態の集合について、これはnfaにおける受理状態を要素に持つような状態なので、以下の4つが該当する。

$\{t_1\}$
$\{t_7\}$
$\{t_5, t_{11}\}$
$\{t_{11}\}$

以上からこのdfa$D_2$を状態遷移図にしてみる…前に。

再度になるが、状態の名前を書き換えさせてもらう。

上の表の上から、$t_0, t_1, …, t_7$だ。

分かりづらいので、この置き換えた後の状態遷移の様子も表にしておこう。

現状態	$1$	$+$
$t_0$	$t_1$	$t_7$
$t_1$	$t_2$	$t_3$
$t_2$	$t_2$	$t_4$
$t_3$	$t_5$	$t_7$
$t_4$	$t_6$	$t_7$
$t_5$	$t_2$	$t_3$
$t_6$	$t_2$	$t_4$
$t_7$	$t_7$	$t_7$

$D_2$の状態遷移関数内訳

これに置き換えた場合の初期状態は$t_0$、受理状態の集合は$\{t_1, t_2, t_5, t_6\}$だ。

この書き直した状態で、$D_2$の状態遷移図を書いてみた。

ステップ5：$D_1$と$D_2$の等価性

最後にこれだ。

二つのdfaが等価であるとはどういうことだったかは、以下の記事を参照だ。

さて、この中で等価性の判定アルゴリズムを紹介しているが…

ちょっと、ここでは別の方法を使おう。

何かというと、$D_2$を既約に直す。

既約についてと、既約への変形方法は上の記事内に書いてある。

そして、この既約に直したdfaと$D_1$が同型であれば、等価であると示すことができる。

この同型については以下の記事をご覧いただきたい。

というわけで、ステップ4までで作ったdfa$D_2$を既約にしていく…のだが。

ちょっと、あまりにオマケが長くなりすぎているので、過去に作成したプログラムを使って直させてもらう。

そのプログラムは以下の記事で紹介している。

これに$D_2$の情報を入力し、既約に変換して出力してみた結果が以下だ。

入力したdfaの情報
状態：
	t_0
	t_2
	t_1
	t_4
	t_3
	t_6
	t_5
	t_7
入力記号：
	{1, +}
状態遷移関数：
	δ(t_0, 1) = t_1
	δ(t_0, +) = t_7
	δ(t_2, 1) = t_2
	δ(t_2, +) = t_4
	δ(t_1, 1) = t_2
	δ(t_1, +) = t_3
	δ(t_4, 1) = t_6
	δ(t_4, +) = t_7
	δ(t_3, 1) = t_5
	δ(t_3, +) = t_7
	δ(t_6, 1) = t_2
	δ(t_6, +) = t_4
	δ(t_5, 1) = t_2
	δ(t_5, +) = t_3
	δ(t_7, 1) = t_7
	δ(t_7, +) = t_7
初期状態：t_0
受理状態：
	t_2
	t_1
	t_6
	t_5
-----------------------------------------------------------------------
既約に変形したdfaの情報
状態：
	[t_2, t_1, t_6, t_5]
	[t_0, t_4, t_3]
	t_7
入力記号：
	{1, +}
状態遷移関数：
	δ([t_2, t_1, t_6, t_5], 1) = [t_2, t_1, t_6, t_5]
	δ([t_2, t_1, t_6, t_5], +) = [t_0, t_4, t_3]
	δ([t_0, t_4, t_3], 1) = [t_2, t_1, t_6, t_5]
	δ([t_0, t_4, t_3], +) = t_7
	δ(t_7, 1) = t_7
	δ(t_7, +) = t_7
初期状態：[t_0, t_4, t_3]
受理状態：
	[t_2, t_1, t_6, t_5]

これで、既約形が取得できた。

最後にもう一度名前を以下のように置き換える。

[t_0, t_4, t_3]→$t_0$
[t_2, t_1, t_6, t_5]→$t_1$

これで、上のプログラムで得られた$D_2$の既約形の状態遷移図を書いてみよう。

これと、$D_1$の状態遷移図を見比べてみる。

$t_0$を$s_0$、$t_1$を$s_1$、$t_7$を$\phi$に置き換えてあげれば、完全に一致することが分かる。

よって、具体例で作った正規表現は問題ないことが証明できた。

…オマケなのに非常に長くなってしまったが、いいタイミングなのでこれを通してこれまでの内容も思い出しておこう。

現状態	\(1\)	\(+\)
\(\phi\)	\(\phi\)	\(\phi\)
\(\{s_0\}\)	\(\{s_1\}\)	\(\phi\)
\(\{s_1\}\)	\(\{s_1\}\)	\(\{s_0\}\)
\(\{s_0, s_1\}\)	\(\{s_1\}\)	\(\{s_0\}\)

状態\(s\)	対応\(S(s)\)
\(t_0\)	\(\{t_0\}\)
\(t_1\)	\(\{t_1, t_2, t_5, t_6, t_8, t_{11}\}\)
\(t_2\)	\(\{t_2, t_5, t_6, t_8, t_{11}\}\)
\(t_3\)	\(\{t_3, t_4\}\)
\(t_4\)	\(\{t_4\}\)
\(t_5\)	\(\{t_2, t_5, t_6, t_8, t_{11}\}\)
\(t_6\)	\(\{t_6, t_8, t_{11}\}\)
\(t_7\)	\(\{t_7, t_8, t_{11}\}\)
\(t_8\)	\(\{t_8, t_{11}\}\)
\(t_9\)	\(\{t_9, t_{10}\}\)
\(t_{10}\)	\(\{t_{10}\}\)
\(t_{11}\)	\(\{t_6, t_8, t_{11}\}\)

現状態	\(1\)	\(+\)
\(t_0\)	\(\{t_1\}\)	\(\phi\)
\(t_1\)	\(\{t_7\}\)	\(\{t_3, t_9\}\)
\(t_2\)	\(\{t_7\}\)	\(\{t_3, t_9\}\)
\(t_3\)	\(\{t_5\}\)	\(\phi\)
\(t_4\)	\(\{t_5\}\)	\(\phi\)
\(t_5\)	\(\{t_7\}\)	\(\{t_3\, t_9\}\)
\(t_6\)	\(\{t_7\}\)	\(\{t_9\}\)
\(t_7\)	\(\{t_7\}\)	\(\{t_9\}\)
\(t_8\)	\(\{t_7\}\)	\(\{t_9\}\)
\(t_9\)	\(\{t_{11}\}\)	\(\phi\)
\(t_{10}\)	\(\{t_{11}\}\)	\(\phi\)
\(t_{11}\)	\(\{t_7\}\)	\(\{t_9\}\)

現状態	\(1\)	\(+\)
\(\{t_0\}\)	\(\{t_1\}\)	\(\phi\)
\(\{t_1\}\)	\(\{t_7\}\)	\(\{t_3, t_9\}\)
\(\{t_7\}\)	\(\{t_7\}\)	\(\{t_9\}\)
\(\{t_3, t_9\}\)	\(\{t_5, t_{11}\}\)	\(\phi\)
\(\{t_9\}\)	\(\{t_{11}\}\)	\(\phi\)
\(\{t_5, t_{11}\}\)	\(\{t_7\}\)	\(\{t_3, t_9\}\)
\(\{t_{11}\}\)	\(\{t_7\}\)	\(\{t_9\}\)
\(\phi\)	\(\phi\)	\(\phi\)

現状態	\(1\)	\(+\)
\(t_0\)	\(t_1\)	\(t_7\)
\(t_1\)	\(t_2\)	\(t_3\)
\(t_2\)	\(t_2\)	\(t_4\)
\(t_3\)	\(t_5\)	\(t_7\)
\(t_4\)	\(t_6\)	\(t_7\)
\(t_5\)	\(t_2\)	\(t_3\)
\(t_6\)	\(t_2\)	\(t_4\)
\(t_7\)	\(t_7\)	\(t_7\)

オートマトン・言語と計算理論「正規表現とnfaの関係」

今回証明する定理

定義：nfaの部分

定義：nfaが認識する言語を生成する正規表現

初期段階

帰納段階

具体例

おわりに

オマケ：具体例が正しいことの証明

ステップ1：nfa\(N\)をdfaに変換

ステップ2：正規表現\(Reg(N)\)を\(\varepsilon\)nfaに変換

ステップ3：\(\varepsilon\)nfa\(E\)をnfaに変換

ステップ4：nfa\(N’\)をdfaに変換

ステップ5：\(D_1\)と\(D_2\)の等価性

コメント

2024年4月
日	月	火	水	木	金	土
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30