java - 如何简化从 DFA 生成的正则表达式

Question

我尝试使用 Java 实现 Brzozowski 代数方法，以生成给定 DFA 接受的语言的正则表达式，生成的表达式是正确的，但没有简化。

例如:E|(E)e(e)|(A|(E)e(A))(A|e|(B)e(A))*(B|(B)e(e))| (B|(E)e(B)|(A|(E)e(A))(A|e|(B)e(A))*(E|(B)e(B)))(B |e|(E)e(B)|(A|(E)e(A))(A|e|(B)e(A))*(E|(B)e(B)))*( E|(E)e(e)|(A|(E)e(A))(A|e|(B)e(A))*(B|(B)e(e)))(e = epsilon，E = 空集)

代替:(A|B)*AB

“传递闭包方法”返回几乎相同的结果。

其中一个解决方案包括最小化自动机，但我认为生成简化的正则表达式太重了。

另外，使用 Java 正则表达式方法来简化正则表达式一点也不漂亮:)。

所以，如果能帮我找到解决方案就好了。

Answer 1

是的，这是可能的。看看这个Peter Norvig article .哦!有一个 second part .解决方案是在 python 中，但您可以轻松地对其进行调整。