正規表現で文字列の否定⑥
以下のWebサイトの「補足資料 (5)」に沿ってDFAを正規表現に変換するC#のメソッドを書こうとしているところ。
www.nue.ie.niigata-u.ac.jp
2ページ目の「GNFAの等価変換」は、さらっとななめ読みしただけだと分からなかったので、例2を自分で解いてみた。
を削除することに決める
これから除去される部分を赤色にしているよ!んで、その他の辺のラベルが更新されるよ!
![](https://cdn-ak.f.st-hatena.com/images/fotolife/y/yagiey/20220602/20220602203714.png)
から
への辺を更新する
を黄色、
を緑、
を紫、
を赤で描いてるよ。つまり、
で更新されるよ。
![](https://cdn-ak.f.st-hatena.com/images/fotolife/y/yagiey/20220602/20220602203917.png)
から
への辺を更新する
同様に色分けしているよ。結果、で更新されるよ。
![](https://cdn-ak.f.st-hatena.com/images/fotolife/y/yagiey/20220602/20220602205527.png)
から
への辺を更新する
結果、で更新されるよ。
![](https://cdn-ak.f.st-hatena.com/images/fotolife/y/yagiey/20220602/20220602210624.png)
変換後のGNFA ![N_{2}](https://chart.apis.google.com/chart?cht=tx&chl=N_%7B2%7D)
で更新したラベルを簡略化してるよ。
にはまだ除去可能な状態
があるので、
に対して「GNFAの等価変換」をもう一回やるよ!
![](https://cdn-ak.f.st-hatena.com/images/fotolife/y/yagiey/20220602/20220602211204.png)
を削除することに決める
これから除去される部分を赤色にしているよ!んで、その他の辺のラベルが更新されるよ!
![](https://cdn-ak.f.st-hatena.com/images/fotolife/y/yagiey/20220602/20220602212050.png)
から
への辺を更新する
結果、で更新されるよ。
![](https://cdn-ak.f.st-hatena.com/images/fotolife/y/yagiey/20220602/20220602212835.png)
できた!
![](https://cdn-ak.f.st-hatena.com/images/fotolife/y/yagiey/20220602/20220602212937.png)