この正規表現をさらに単純化することは可能ですか？

Question

コンパイラクラスの宿題に取り組んでいますが、次の問題があります：

奇数の a を含む a と b のすべての文字列に正規表現を記述します奇数の b （またはその両方）。

多くのホワイトボード作業の後、次の解決策を思いつきました：

(aa|bb)* (ab|ba|a|b) ((aa|bb)* (ab|ba) (aa|bb)* (ab|ba) (aa|bb)*)*

ただし、これは私が入手できる最も単純化されたものですか？簡素化に役立つかどうかを確認するために、州の数を最小限に抑えるようにDFAを構築することを検討しましたが、まずSOで正規表現の指導者に尋ねるつもりでした。

Answer 1

a（aa）*から始めてそこから進むというGreg Dの推奨事項を確認してください。 Sepp2kにはほぼ正解がありますが、本当の考慮事項は、他の手紙を気にしないことです。つまり、「奇数」を見ると、制約では、文字列にbが含まれているかどうかはまったく気にしません。したがって、b *をできる限り貼り付けてください：）

Sepp2kの答えはほぼ正しいですが、これは正しいです：

b* a b* (a b* a b* )* | a* b a* (b a* b a* )*

詳しく説明すると、この正規表現は、奇数のa（最初のセクション）を持つすべての文字列と、奇数のbを含む任意の文字列を持つそれらの文字列のORを計算します。

Answer 2

これは動作するはずです：

b* a b* (a b* a b*)* |  a* b a* (b a* b a*)*

Answer 3

あなたの書かれた正規表現が正しいとは思わないのではないでしょうか。文字列を考慮してください：

aba

マッチにはいくつかの選択肢がありますが、長さが奇数であるという事実は、先頭の1つのaとマッチしなければならないことを意味します。

(a)(ba)

しかし、残念ながら、そこにある2番目のメイングループを一致させることはできません（ba）。

このような制約を扱うとき、コアの制約から始めてそこから進む方が簡単であることがわかりました。この場合、制約は「奇数」です。で始まる

a(aa)*

奇数の a を強制してそこから移動します。 ：）

Answer 4

問題に別のアプローチをする必要があると思います。

a と b の両方の偶数を持たないものに一致させようとしています。

a と b の偶数の数字に一致するものから始める方がおそらく簡単でしょう。その時点で行う必要があるのは、実際に一致させたい最小の文字列に一致するものを最後に追加することだけです。