以下の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+$ でいいかと思…

まずは文字列abを含まない文字列から考えてみた。僕ははあまり賢くないので、いきなり正規表現で考えると分からなくなりそうだったので、状態遷移図を描きつつ、有限オートマトンM0を構成してみた。オレンジ色の状態が受理状態で、いったん状態3に到達したら…

bynatures.hatenadiary.jp を読んで、「正規表現は否定を上手く表せない？マジか！！」って思ったので、やってみた。とりあえず、紹介されている例を確かめてみた。 https://ideone.com/a38njo ん...？？なんか変じゃね？？

正規表現→ε動作ありNFA→ε動作なしNFA→DFAをやるコードを書いてGitHubにpushしといたよ。 github.com やり残してることは以下。 DFAの最小化 一回以上の繰り返し（+）の導入 (0|1|2|3|4|5|6|7|8|9)を[0-9]って書けるようにする 任意の位置文字を表す文字（.）…

３年くらい前、実数を表す文字列を受理するオートマトンを実装してみた。 最近、簡単な正規表現をDFAに変換するコードを書いてみてるけど、その中で、過去書いた日記に誤りを見つけたので、訂正しておく。