C# と VB.NET の質問掲示板

わんくま同盟

ASP.NET、C++/CLI、Java 何でもどうぞ

C# と VB.NET の入門サイト

■99488 / 5階層)  正規表現で文字列の否定
□投稿者/ 匿名希望マン (4回)-(2022/04/16(Sat) 18:01:22)
やりたいことは、
 ・文字列aを含まない文字列 → これは自明。[^a]*
 ・文字列abを含まない文字列
 ・文字列abcを含まない文字列
 ・...
っていくつか(規則性が見えるまで)求めていって、一般項(?)を求めたいのです。

...ってことで、まずは文字列abを含まない文字列を考えました。
私はあまり賢くないので、いきなり正規表現で考えると分からなくなりそうだったので、
状態遷移図を書きながら、有限オートマトンM0<Q,Σ,δ,q0,F>を構成してみました。
図を投稿できれば良いんですけど、できなさそうなので全部文字で書きます。

・状態集合Q= {0,1,2,3}
・アルファベットΣ= {a,b,c}
・初期状態q0= 0
・受理状態F= {0,1,2}
・状態遷移表δは以下。
 ┏━┳━┳━┳━┓
 ┃ ┃a┃b┃c┃
 ┣━╋━╋━╋━┫
 ┃0┃1┃2┃2┃
 ┃1┃1┃3┃0┃
 ┃2┃1┃2┃2┃
 ┗━┻━┻━┻━┛
aでもbでもない入力すべてをcとします。
いったん状態3に到達したら、必ず不受理となります。

遷移表から判断するに、状態0と状態2は等価なようです。
これらをまとめて、整理して、M1<Q,Σ,δ,q0,F>としてみました。

・Q= {0,1,2}
・Σ= {a,b,c}
・q0= 0
・F= {0,1}
・δは以下。
 ┏━┳━┳━┳━┓
 ┃ ┃a┃b┃c┃
 ┣━╋━╋━╋━┫
 ┃0┃1┃0┃0┃
 ┃1┃1┃2┃0┃
 ┗━┻━┻━┻━┛

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

編集キー/

前の記事(元になった記事) 次の記事(この記事の返信)
←Re[4]: 正規表現で文字列の否定 /匿名希望マン →Re[6]: 正規表現で文字列の否定 /伝説のカレー
 
上記関連ツリー

正規表現で文字列の否定 / 匿名希望マン (22/04/14(Thu) 20:20) #99465
Re[1]: 正規表現で文字列の否定 / 774RR (22/04/15(Fri) 09:43) #99470
Re[1]: 正規表現で文字列の否定 / furu (22/04/15(Fri) 10:48) #99473
  └ Re[2]: 正規表現で文字列の否定 / 匿名希望マン (22/04/15(Fri) 14:01) #99475
    └ Re[3]: 正規表現で文字列の否定 / shu (22/04/15(Fri) 14:55) #99477
      └ Re[4]: 正規表現で文字列の否定 / 匿名希望マン (22/04/15(Fri) 20:27) #99479
        ├ 正規表現で文字列の否定 / 匿名希望マン (22/04/16(Sat) 18:01) #99488 ←Now
        │└ Re[6]: 正規表現で文字列の否定 / 伝説のカレー (22/04/16(Sat) 18:12) #99489
        │  └ Re[7]: 正規表現で文字列の否定 / 匿名希望マン (22/04/16(Sat) 20:35) #99491
        └ Re[5]: 正規表現で文字列の否定 / 伝説のカレー (22/04/16(Sat) 17:10) #99487
          └ Re[6]: 正規表現で文字列の否定 / 匿名希望マン (22/04/17(Sun) 12:17) #99493 解決済み
            └ Re[7]: 正規表現で文字列の否定 / shu (22/04/18(Mon) 17:29) #99499
              └ Re[8]: 正規表現で文字列の否定 / 匿名希望マン (22/04/19(Tue) 22:08) #99502
                └ Re[9]: 正規表現で文字列の否定 / shu (22/04/22(Fri) 01:19) #99529
                  └ Re[10]: 正規表現で文字列の否定 / 匿名希望マン (22/05/29(Sun) 14:48) #99776 解決済み
                    └ Re[11]: 正規表現で文字列の否定 / 匿名希望マン (22/05/29(Sun) 14:56) #99777 解決済み
                      └ Re[12]: 正規表現で文字列の否定 / 匿名希望マン (22/06/12(Sun) 23:04) #99841 解決済み

上記ツリーを一括表示 / 上記ツリーをトピック表示
 
上記の記事へ返信