regex - a と偶数個の b を含む文字列の正規表現

Question

次の言語を特徴とする正規表現を定義する方法は?

L = {w ∈ {a, b}* | w の b は偶数です}

関連するオートマトンを作成しようとしました：

それから、アルゴリズムを適用してDFAから正規表現を取得しようとしたところ、次の式が得られましa*ba*bた。

これが正しい答えでしょうか？

Answer 1

近いですが、パターンa*の最後に a が必要です。また、アンカーが必要で、文字列の開始^と$終了を指定する必要があります。次に、すべての正規表現をキャプチャ グループ内に配置し、*偶数の場合に一致させるために使用できます。 b、および のa*ゼロ数b:

 ^((a*ba*ba*)*|a*)$

注:|は論理 OR であり、正規表現エンジンを(a*ba*ba*)*orに一致させますa*。

Debuggex デモ

よりエレガントにすることもできますが、最初に正規表現にあまり慣れていないため、前のパターンを提案しました。

たとえば、次のように動作します。

^(((a*b){2})*)a*$

Answer 2

DFAから正規表現への変換アルゴリズムに従っているため（ペンで実行）、これが最良の解決策です。

(a*|ba*b)*

ここでテストできます。また、このビデオを見てこのアルゴリズムについて学ぶことができます。