是否可以进一步简化这个正则表达式？
我正在为我的编译器类做一些家庭作业，但遇到以下问题：
为包含 a 和 b 的所有字符串编写正则表达式奇数个 a 或奇数个 b（或两者）。
经过大量的白板工作后，我想出了以下解决方案：
(aa|bb)* (ab|ba|a|b) ((aa|bb)* (ab|ba) (aa|bb)* (ab|ba) (aa|bb)*)*
但是，这是我能得到的最简化的解决方案吗？我考虑过构建 DFA，试图尽量减少那里的状态数量，看看它是否能帮助我简化，但我想我应该先向正则表达式专家询问。
I'm working on some homework for my compiler class and I have the following problem:
Write a regular expression for all strings of a's and b's that contain an odd number of a's or an odd number of b's (or both).
After a lot of whiteboard work I came up with the following solution:
(aa|bb)* (ab|ba|a|b) ((aa|bb)* (ab|ba) (aa|bb)* (ab|ba) (aa|bb)*)*
However, Is this is the most simplified I can get it? I've considered constructing the DFA trying to minimize the number of states there to see if it would help me simplify but I figured I would ask the regex gurus on SO first.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
采纳 Greg D 的建议，即从 a(aa)* 开始，然后从那里开始。 Sepp2k 几乎是正确的，但真正的考虑是你不关心另一个字母。我的意思是，当您查看“a 的奇数”约束时，您根本不关心字符串中的 b 是什么。因此，将 b* 粘贴在任何可以的地方:)
Sepp2k 的答案几乎是正确的，但这个是正确的：
详细来说，这个正则表达式计算出所有具有奇数个 a 的字符串（第一部分），并将这些字符串与任何包含奇数个 b 的字符串。
Take Greg D's recommendation of starting with a(aa)*, and going from there. Sepp2k almost has it right, but the real consideration is that you don't care about the other letter. What I mean is, when you are looking at the "odd number of a's" constraint, you don't care at all about what b's are in your string. Thus, stick b*'s anywhere you can :)
Sepp2k's answer is almost right, but this one is correct:
To elaborate, this regex figures out all strings with an odd number of a's (first section), and OR's those strings with any strings containing an odd number of b's.
这应该有效：
This should work:
恐怕我不相信你写的正则表达式是正确的。考虑字符串：
我们有几个匹配选择，但事实上它是奇数长度，这意味着我们必须在前面匹配一个单独的 a，所以：
但是，遗憾的是，你的第二个主要分组不可能匹配 (ba) 。
当处理这样的约束时，我发现从核心约束开始并从那里开始更容易。在这种情况下，您的约束是“奇数”，因此首先
强制使用奇数个
a，然后从那里开始。 :)I'm afraid that I don't believe your regex as written is correct. Consider the string:
We have a couple choices for matches, but the fact that it's odd-length means we must match a lone a at the front, so:
But, sadly, it's impossible for your second main grouping there to match (ba).
When dealing with a constraint like this, I found it easier to start from the core constraint and go from there. In this case, your constraint is "odd," so start with
to force an odd number of
a's and go from there. :)我认为你需要以不同的方式处理这个问题。
您正在尝试匹配
a和b均不为偶数的任何内容。从匹配偶数个
a和b的东西开始可能会更容易。此时您所要做的就是在末尾添加一些与您实际想要匹配的最小字符串相匹配的内容。I think you need to approach the problem differently.
You are trying to match anything that doesn't have even numbers of both
aandb.It would probably be easier to start with something that matches even numbers of
aandb. All you have to do at that point would be to add something on the end that matches the smallest string that you actually want to match.