正则表达式等价

Question

有没有办法找出两个任意正则表达式是否等价？对我来说看起来很复杂的问题，但可能有一些 DFA 简化机制之类的？

Answer 1

要测试等价可以计算href="http://www.google.de/search?hl=en&q=minimal+dfa" rel="noreferrer">最小的DFA ，在表达式

Answer 2

平等的可测性是正则表达式的经典性质之一。 （注：这如果你真的在谈论Perl的正则表达式或一些其他技术上不成立的非正规的superlanguage。）

将您的RE广义有限自动机A和B，然后构造一个新的自动机A-B，使得A的接受状态为空转变到B的开始状态，而B的接受状态被反转。这给你接受所有那些由A可接受字符串，除了所有那些由B.接受自动机

做B-A是相同的，并且两个减少到纯的FA。如果英足总从开始状态访问没有接受状态则接受空语言。如果可以表明，无论是A-B和B-A是空的，你已经表明，A = B。

Edit嘿，我不能相信没有人注意到巨大的错误 - 故意之一，当然:-P的

如所描述的将接受这些字符串，其前半部分被A接受并且其第二半不受B.建立接受期望的 A-B是一个稍微麻烦过程自动机A-B。我不能把它从我的头顶，但我知道这是明确的（可能包括创建状态的代表接受在A和B中的非接受状态状态的产品）。

Answer 3

这真的取决于你所说的正则表达式是什么。正如其他海报指出，减少两个表达式他们最小的DFA应该工作，但它仅适用于纯粹的正则表达式。

一些在现实世界中的正则表达式库使用的结构（特别是反向引用）给他们力量来表达都是不正规的语言，所以DFA算法将不为他们工作。例如，正则表达式：([a-z]*) \1相同单词由空格分隔（a a和b b但不b a也不a b）的双occurence匹配。这不能由一个有限自动机在所有识别。

Answer 4

这两个 Perlmonks 线程讨论了这个问题（具体来说，请阅读 blokhead 的回复）：

• 正则表达式的比较可满足性
• 测试正则表达式的等价性