正規表現で文字列の否定⑥

正規表現 オートマトン

以下のWebサイトの「補足資料 (5)」に沿ってDFAを正規表現に変換するC#のメソッドを書こうとしているところ。
www.nue.ie.niigata-u.ac.jp
2ページ目の「GNFAの等価変換」は、さらっとななめ読みしただけだと分からなかったので、例2を自分で解いてみた。

まずは変換前のDFA M_{1}と、変換後のGNFA N_{1}

変換前のDFA M_{1}
変換後のGNFA N_{1}

q_{1}を削除することに決める

これから除去される部分を赤色にしているよ！んで、その他の辺のラベルが更新されるよ！

除去される状態と辺

q_{start}からq_{2}への辺を更新する

R_{1}を黄色、R_{2}を緑、R_{3}を紫、R_{4}を赤で描いてるよ。つまり、\epsilon a*b\cup\emptysetで更新されるよ。

q_{start}からq_{2}への辺を更新する

q_{start}からq_{accept}への辺を更新する

同様に色分けしているよ。結果、\epsilon a*\emptyset \cup\emptysetで更新されるよ。

q_{start}からq_{accept}への辺を更新する

q_{2}からq_{accept}への辺を更新する

結果、\emptyset a*\emptyset\cup\epsilonで更新されるよ。*1

q_{2}からq_{accept}への辺を更新する

q_{2}からq_{2}への辺を更新する

結果、\emptyset a*b\cup(a\cup b)で更新されるよ。

q_{2}からq_{2}への辺を更新する

変換後のGNFA N_{2}

R_{1}R_{2}*R_{3}\cup R_{4}で更新したラベルを簡略化してるよ。N_{2}にはまだ除去可能な状態q_{2}があるので、N_{2}に対して「GNFAの等価変換」をもう一回やるよ！

変換後のGNFA N_{2}

q_{2}を削除することに決める

これから除去される部分を赤色にしているよ！んで、その他の辺のラベルが更新されるよ！

q_{2}を削除することに決める

q_{start}からq_{accept}への辺を更新する

結果、a*b(a\cup b)*\epsilon *\cup\emptysetで更新されるよ。

q_{start}からq_{accept}への辺を更新する

できた！

変換完了

*1:2022/06/02 17:00現在、PDFでは \epsilon a*\emptyset\cup\epsilon と記載されているけど、これは誤植だそうです。新潟大学の青戸先生にメールで確かめたよ！