| やりたいことは、
・文字列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とします。
いったん状態3に到達したら、必ず不受理となります。
遷移表から判断するに、状態0と状態2は等価なようです。
これらをまとめて、整理して、M1<Q,Σ,δ,q0,F>としてみました。
・Q= {0,1,2}
・Σ= {a,b,c}
・q0= 0
・F= {0,1}
・δは以下。
┏━┳━┳━┳━┓
┃ ┃ａ┃ｂ┃ｃ┃
┣━╋━╋━╋━┫
┃０┃１┃０┃０┃
┃１┃１┃２┃０┃
┗━┻━┻━┻━┛
この決定性有限オートマトンM1を、それと等価な正規表現に変換したい...。
どうすりゃ良いのかなーーー？
|