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

文字列処理でやってみた とりあえず ここ で以下の16個の正規表現を生成して、それらのルールを分析して、C#のメソッド作ってみたよ。 Regex01：文字列"0"を含まない任意の文字列とマッチする正規表現 Regex02：文字列"01"を含まない任意の文字列とマッチす…

以下のオートマトンを構成してみた。出現する状態はすべて受理状態。 M2 文字列abを含まない任意の文字列を受理するDFA M3 文字列abcを含まない任意の文字列を受理するDFA M4 文字列abcdを含まない任意の文字列を受理するDFA M5 文字列abcdeを含まない任意の…

前回提示したM1の状態2は無いのと同じなので、等価なオートマトンM2は次のようになる。 文字列abを含まない任意の文字列を受理するDFA([^a]|a+[^ab])* で状態0から状態0への遷移で、続けて a+ で状態1への遷移。 まとめて ^([^a]|a+[^ab])*a+$ でいいかと思…