regex - 是否可以进一步简化这个正则表达式？

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 的建议从 a(aa)* 开始，然后从那里开始。Sepp2k 几乎是正确的，但真正的考虑是你不关心另一个字母。我的意思是，当您查看“a 的奇数”约束时，您根本不关心字符串中的 b 是什么。因此，将 b*'s 贴在任何可以的地方 :)

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

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

(a)(ba)

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

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

a(aa)*

强制奇数个a' 并从那里开始。:)

Answer 4

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

您正在尝试匹配任何既不是偶数又是a和的东西b。

从匹配偶数个a和的东西开始可能会更容易b。那时您所要做的就是在末尾添加一些与您实际想要匹配的最小字符串匹配的内容。