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

わんくま同盟

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

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


■99488 / )  Re[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を、それと等価な正規表現に変換したい...。
どうすりゃ良いのかなーーー?

返信 編集キー/


管理者用

- Child Tree -