是否有可能进一步简化这个正则表达式？

Question

我正在为我的编译器类做一些功课，我有以下问题：

为 a 和 b 的所有字符串写一个正则表达式，其中包含奇数个 a 或者奇数个 b （或两者）。

经过大量的白板工作后，我提出了以下解决方案：

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

然而，这是我能得到的最简化的吗？我已经考虑过构建DFA，试图最大限度地减少那里的状态数量，看看它是否有助于我简化，但我想我会首先询问正则表达式专家。

Answer 1

采取Greg D的建议，从（aa）*开始，然后从那里开始。 Sepp2k几乎是正确的，但真正的考虑因素是你不关心另一封信。我的意思是，当你在看“a的奇数”时约束，你根本不关心字符串中的b是什么。因此，坚持b *的任何地方你可以：）

Sepp2k的回答几乎是正确的，但这个是正确的：

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

详细说明，这个正则表达式计算出所有带有奇数个a（第一个部分）的字符串，而OR是那些带有包含奇数个b的字符串的字符串。

Answer 2

这应该有效：

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

Answer 3

我担心我不相信你写的正则表达是正确的。考虑字符串：

aba

我们有几个比赛的选择，但事实上它是奇数长度意味着我们必须匹配前面的孤独a，所以：

(a)(ba)

但是，遗憾的是，你的第二个主要分组不可能匹配（ba）。

当处理这样的约束时，我发现从核心约束开始更容易并从那里开始。在这种情况下，您的约束是“奇数”，所以从

开始

a(aa)*

强制使用奇数个 a 并从那里开始。 ：）

Answer 4

我认为你需要以不同的方式解决问题。

您正在尝试匹配任何没有偶数 a 和 b 的数据。

可能更容易从匹配甚至 a 和 b 的数字开始。那时你要做的就是在末尾添加一些与你想要匹配的最小字符串相匹配的东西。