regex - 简化这个正则表达式

Question

我正在为我的编译器类做一些考前练习，需要简化这个正则表达式。

(a U b)*(a U e)b* U (a U b)*(b U e)a*

很明显，e 是空字符串，而 U 代表联合。

到目前为止，我认为 (a U b)* 之一可以删除，作为 a U a = a 的并集。但是，我找不到任何其他简化，并且到目前为止在其他问题上做得并不好。 :(

任何帮助表示赞赏，非常感谢!

Answer 1

首先翻译成该语言的英文描述:

(a U b)*(a U e)b* U (a U b)*(b U e)a*

转换为:
a 的任意序列s 或 b s，后跟一个可选的 a ，后跟任意数量的 b s。

或者

任意数量的 a s 和 b s，后跟一个可选的 b , 后面是任意数量的 a秒

这里有很多重叠 - 至少 (a U b)*(a U e)与 (a U b)* 完全相同，因为“任何 a s 和 b s 的序列”都必须以 a 结尾或 epsilon(因为任何字符串都可以以 epsilon 结尾)所以可以消除这些组，留下

(a U b)*b* U (a U b)*a*

转换为:
a 的任意序列s 或 b s，后跟任意数量的 b s。

或者

任意数量的 a s 和 b s，后跟任意数量的 a秒

现在最外层组的第一部分是相同的，所以让我们将它们合并为一个

(a U b)*(a* U b*)

转换为:
a 的任意序列s 或 b s，后跟任意数量的 a s OR 任意数字 b s。

现在等一下，“A 和 B 的任何序列”必然以“ a s 的任何序列或 b s 的任何序列”结尾，这意味着任何匹配第一部分的东西都可以匹配整个正则表达式(因为第二部分的长度可以为零)所以我们为什么不让它

(a U b)*

达。简单的。