regex - **手工简化正则表达式的技术**

Question

我试图证明 RE

s(bs)*[(abb*a*)*ab]*aa(a∪b)在哪里s=b*a*ab

可以简化为

(a∪b)*abaa(a∪b),

但是我知道的所有一般转换，例如(ab)*a=a(ba)*或(a*b)*a*=(a∪b)*似乎没有效果。

所以问题是：

1. 一步一步的转变过程在这里可行吗？如果是这样，你能告诉我它是如何完成的吗？
2. 如果证明需要其他类型的技术，它们是什么？
3. 是否有一个清晰而全面的参考解释用于简化正式 RE 的技术？

谢谢。

Answer 1

有很多方法可以做到这一点。

一种简单的方法是将正则表达式转换为 NFA。查看两个 NFA 是否识别相同的语言：

1. 考虑两个 NFA 的起始状态。

2. 对每个 NFA 考虑的状态进行 epsilon 闭包。

3. 如果一个 NFA 的状态集至少包含一个接受状态，但另一个 NFA 的状态集不包含接受状态，则 NFA 不相等，您就完成了。

4. 否则，对于每个符号，按照该符号为每个 NFA 获取一组新状态，然后返回步骤 1。

这将采取有限数量的步骤，因为要考虑的状态集数量有限。

您还可以将两个正则表达式都转换为最小 DFA 并显示它们是同构的，但这种技术实际上与上述技术完全相同，只是步骤的顺序不同。

插图

考虑 REaa*和a*a。很明显，它们识别相同的语言，但我们将使用它们来说明算法。

1. 首先，我们考虑每个 NFA 的起始状态。这些{1}用于左 RE 和{1}右 RE，我们将其写为{1},{1}.

2. 然后我们采用 epsilon 闭包，即{1},{1,2}.

3. 这两个集合都不包含结束状态，所以我们继续。

4. 传出的符号是 only a，所以我们采取所有a的转换来获得{2},{1,3}。

5. epsilon 闭包是{2,3},{1,2,3}.

6. 两者都包含结束状态，所以我们继续。

7. 同样，传出符号是a，因此我们采用所有a转换来获得{2},{1,3}。

8. epsilon 闭包是{2,3},{1,2,3}. 这与第 5 步相同，因此我们不再重复。

由于没有其他要检查的内容，我们就完成了，并且两者已被证明是相同的。