2022-05-20 正規表現で文字列の否定③ 正規表現 オートマトン 前回提示した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が受理状態ではなくなってしまった。