正则表达式等价

有没有办法找出两个任意正则表达式是否相同？看起来像复杂的问题,但可能有一些DFA简化机制或什么？

要测试等效性,您可以计算表达式的最小DFA并进行比较.

可测性的相等性是正则表达式的经典属性之一.(注意:如果您真的在谈论Perl正则表达式或其他一些技术上不规则的超语言,那么这就不成立了.)

将你的RE转换为广义有限自动机A和B,然后构造一个新的自动机AB,使得A的接受状态具有到B的起始状态的空转换,并且B的接受状态被反转.这为您提供了一个自动机,它接受A接受的所有字符串,但B接受的所有字符串除外.

为BA做同样的事情,并将两者都减少到纯粹的FAs.如果FA没有从开始状态可访问的接受状态,则它接受空语言.如果你可以证明AB和BA都是空的,那你就表明A = B.

Edit 嘿,我简直不敢相信没有人注意到那里的巨大错误 - 当然是故意的错误:-p

所描述的自动机AB将接受那些其前半部分被A接受并且其后半部分不被B接受的字符串.构建所需的 AB是一个稍微棘手的过程.我无法想到这一点,但我确实知道它的定义很明确(并且可能涉及创建状态以表示接受A中的状态和B中的非接受状态的产品).