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

以下の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}
続きを読む

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

文字列処理でやってみた

とりあえず ここ で以下の16個の正規表現を生成して、それらのルールを分析して、C#のメソッド作ってみたよ。

  • Regex01:文字列"0"を含まない任意の文字列とマッチする正規表現
  • Regex02:文字列"01"を含まない任意の文字列とマッチする正規表現
  • Regex03:文字列"012"を含まない任意の文字列とマッチする正規表現
  • ...
  • Regex16:文字列"0123456789ABCDEF"を含まない任意の文字列とマッチする正規表現

github.com

ちなみに、生成して分析していた正規表現は以下。
ルールが見えやすいように、正規表現の縦を合わせてるけど、実際はスペースは無いよ。

Regex01: ^[^0]*$
Regex02: ^([^0]|0+                                                                        [^01])*                                                                                                                              0*$
Regex03: ^([^0]|0(0|10)*                                                                 ([^01]|1[^02]))*                                                                                                                     (0(0|10)*                                                                 1?)?$
Regex04: ^([^0]|0(0|1(0|20))*                                                            ([^01]|1([^02]|2[^03])))*                                                                                                            (0(0|1(0|20))*                                                            (12?)?)?$
Regex05: ^([^0]|0(0|1(0|2(0|30)))*                                                       ([^01]|1([^02]|2([^03]|3[^04]))))*                                                                                                   (0(0|1(0|2(0|30)))*                                                       (1(2?|23))?)?$
Regex06: ^([^0]|0(0|1(0|2(0|3(0|40))))*                                                  ([^01]|1([^02]|2([^03]|3([^04]|4[^05])))))*                                                                                          (0(0|1(0|2(0|3(0|40))))*                                                  (1(2?|234?))?)?$
Regex07: ^([^0]|0(0|1(0|2(0|3(0|4(0|50)))))*                                             ([^01]|1([^02]|2([^03]|3([^04]|4([^05]|5[^06]))))))*                                                                                 (0(0|1(0|2(0|3(0|4(0|50)))))*                                             (1(2?|23(4?|45)))?)?$
Regex08: ^([^0]|0(0|1(0|2(0|3(0|4(0|5(0|60))))))*                                        ([^01]|1([^02]|2([^03]|3([^04]|4([^05]|5([^06]|6[^07])))))))*                                                                        (0(0|1(0|2(0|3(0|4(0|5(0|60))))))*                                        (1(2?|23(4?|456?)))?)?$
Regex09: ^([^0]|0(0|1(0|2(0|3(0|4(0|5(0|6(0|70)))))))*                                   ([^01]|1([^02]|2([^03]|3([^04]|4([^05]|5([^06]|6([^07]|7[^08]))))))))*                                                               (0(0|1(0|2(0|3(0|4(0|5(0|6(0|70)))))))*                                   (1(2?|23(4?|45(6?|67))))?)?$
Regex10: ^([^0]|0(0|1(0|2(0|3(0|4(0|5(0|6(0|7(0|80))))))))*                              ([^01]|1([^02]|2([^03]|3([^04]|4([^05]|5([^06]|6([^07]|7([^08]|8[^09])))))))))*                                                      (0(0|1(0|2(0|3(0|4(0|5(0|6(0|7(0|80))))))))*                              (1(2?|23(4?|45(6?|678?))))?)?$
Regex11: ^([^0]|0(0|1(0|2(0|3(0|4(0|5(0|6(0|7(0|8(0|90)))))))))*                         ([^01]|1([^02]|2([^03]|3([^04]|4([^05]|5([^06]|6([^07]|7([^08]|8([^09]|9[^0A]))))))))))*                                             (0(0|1(0|2(0|3(0|4(0|5(0|6(0|7(0|8(0|90)))))))))*                         (1(2?|23(4?|45(6?|67(8?|89)))))?)?$
Regex12: ^([^0]|0(0|1(0|2(0|3(0|4(0|5(0|6(0|7(0|8(0|9(0|A0))))))))))*                    ([^01]|1([^02]|2([^03]|3([^04]|4([^05]|5([^06]|6([^07]|7([^08]|8([^09]|9([^0A]|A[^0B])))))))))))*                                    (0(0|1(0|2(0|3(0|4(0|5(0|6(0|7(0|8(0|9(0|A0))))))))))*                    (1(2?|23(4?|45(6?|67(8?|89A?)))))?)?$
Regex13: ^([^0]|0(0|1(0|2(0|3(0|4(0|5(0|6(0|7(0|8(0|9(0|A(0|B0)))))))))))*               ([^01]|1([^02]|2([^03]|3([^04]|4([^05]|5([^06]|6([^07]|7([^08]|8([^09]|9([^0A]|A([^0B]|B[^0C]))))))))))))*                           (0(0|1(0|2(0|3(0|4(0|5(0|6(0|7(0|8(0|9(0|A(0|B0)))))))))))*               (1(2?|23(4?|45(6?|67(8?|89(A?|AB))))))?)?$
Regex14: ^([^0]|0(0|1(0|2(0|3(0|4(0|5(0|6(0|7(0|8(0|9(0|A(0|B(0|C0))))))))))))*          ([^01]|1([^02]|2([^03]|3([^04]|4([^05]|5([^06]|6([^07]|7([^08]|8([^09]|9([^0A]|A([^0B]|B([^0C]|C[^0D])))))))))))))*                  (0(0|1(0|2(0|3(0|4(0|5(0|6(0|7(0|8(0|9(0|A(0|B(0|C0))))))))))))*          (1(2?|23(4?|45(6?|67(8?|89(A?|ABC?))))))?)?$
Regex15: ^([^0]|0(0|1(0|2(0|3(0|4(0|5(0|6(0|7(0|8(0|9(0|A(0|B(0|C(0|D0)))))))))))))*     ([^01]|1([^02]|2([^03]|3([^04]|4([^05]|5([^06]|6([^07]|7([^08]|8([^09]|9([^0A]|A([^0B]|B([^0C]|C([^0D]|D[^0E]))))))))))))))*         (0(0|1(0|2(0|3(0|4(0|5(0|6(0|7(0|8(0|9(0|A(0|B(0|C(0|D0)))))))))))))*     (1(2?|23(4?|45(6?|67(8?|89(A?|AB(C?|CD)))))))?)?$
Regex16: ^([^0]|0(0|1(0|2(0|3(0|4(0|5(0|6(0|7(0|8(0|9(0|A(0|B(0|C(0|D(0|E0))))))))))))))*([^01]|1([^02]|2([^03]|3([^04]|4([^05]|5([^06]|6([^07]|7([^08]|8([^09]|9([^0A]|A([^0B]|B([^0C]|C([^0D]|D([^0E]|E[^0F])))))))))))))))*(0(0|1(0|2(0|3(0|4(0|5(0|6(0|7(0|8(0|9(0|A(0|B(0|C(0|D(0|E0))))))))))))))*(1(2?|23(4?|45(6?|67(8?|89(A?|AB(C?|CDE?)))))))?)?$

DFA正規表現に変換する方針に関して

NGワードの長さが増えると状態遷移図がどう変化するかは既にパターンは見えてる。
したがって、NGワードからDFAを作って、それを正規表現に変換すれば良さそう。
なんと、それをやるためのアルゴリズムがあった。ここ の「補足資料 (5)」に沿ってやればできそう。
拙作の正規表現ライブラリに、メソッド(引数はDFA、戻り値は正規表現)として組み込んでみようと思う。

LibreOfficeで二重丸描きたい

オートマトンの受理状態を描くときに、今までオレンジ色で塗りつぶした円を描いてた。
だけど、できれば二重丸でかきたいなーとずっと思ってて、良いやり方見つけた。
基本シェイプの中にある「円」じゃなくて「輪」を使えば良さげ。

円と輪

内側の円も拡大縮小できるので二重線に見えるように拡大してやると良さげ。内側の円はあくまで穴の想定なので、塗りつぶし出来ないっぽい。だけどそれはまた別のアプリ使って何とかしよう。
線のプロパティに「実線」とか「点線」とかあるけど、「二重線」を追加してくれれば、任意のシェイプで二重線使えるのにな。

こうなりました

基本シェイプ「輪」で二重線の円

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

以下のオートマトンを構成してみた。出現する状態はすべて受理状態。

M2
文字列abを含まない任意の文字列を受理するDFA
M3
文字列abcを含まない任意の文字列を受理するDFA
M4
文字列abcdを含まない任意の文字列を受理するDFA
M5
文字列abcdeを含まない任意の文字列を受理するDFA
特定の文字列を含まない任意の文字列を受理するDFAたち

正規表現ここ で生成したよ。
こうやっていくつか描いてみるとパターンに気づくね。
正規表現を自分で生成することは現時点で出来てないけど、DFAなら生成できそうだなー。

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

前回提示したM1の状態2は無いのと同じなので、等価なオートマトンM2は次のようになる。

文字列abを含まない任意の文字列を受理するDFA

([^a]|a+[^ab])* で状態0から状態0への遷移で、続けて a+ で状態1への遷移。
まとめて ^([^a]|a+[^ab])*a+$ でいいかと思ったけど、例えば文字列 ac でダメ(文字列abが含まれていないにも関わらず受理されない)だった。
^([^a]|a+[^ab])*a+$ をDFAにしてみると、以下のようなものだった。

文字列abを含まない任意の文字列を受理するDFA(間違い)

状態0が受理状態ではなくなってしまった。

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

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

決定性有限オートマトンM0

どうやら状態0と状態2は等価なようだ。これらをまとめて、整理して、M1としてみた。

決定性有限オートマトンM1

この決定性有限オートマトンM1を、それと等価な正規表現に変換したいなぁ。
どうすりゃ良いのかな?

なんか良い感じの説明みつけた(2022/04/30 21:18 追記)

www.momoyama-usagi.com
「3.正規表現と有限オートマトン」の「(1) ただの文字列」から「(4) いずれかを表す |」を参考に考えてみよう。

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

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

続きを読む