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

Question

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

写的所有串的正则表达式一个的和b含有奇数个的一个的或奇数的b的(或两者).

经过大量的白板工作后,我想出了以下解决方案:

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

但是,这是我能得到的最简化的吗？我已经考虑构建DFA,试图最小化那里的状态数量,看看它是否会帮助我简化,但我想我会首先询问正则表达式专家.

Answer 1

以Greg D的建议为例,从(aa)*开始,然后从那里开始.Sepp2k几乎是正确的,但真正的考虑因素是你不关心另一封信.我的意思是,当你查看"奇数"的约束时,你根本不关心字符串中的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*)*