有没有办法找出两个任意正则表达式是否相等?对我来说看起来很复杂,但是可能有一些DFA简化机制或者其他什么?正则表达式相等
Q
正则表达式相等
15
A
回答
10
要测试等价你可以计算minimal DFAs的表情和对它们进行比较。
1
这两个Perlmonks线程讨论这个问题(特别是读blokhead的反应):
10
等式的可测性是正则表达式的经典属性之一。 (注:这如果你真的在谈论Perl的正则表达式或一些其他技术上非正规 superlanguage不成立。)
把你的资源来推广有限自动机A和B,然后建立一个新的自动机AB这样A的接受状态具有空转变到B的开始状态,并且B的接受状态被反转。这给你一个自动机,接受A接受的所有字符串,除了所有被B接受的字符串外。
对B-A做同样的事情,并且同时减少到纯粹的FA。如果FA没有从起始状态可访问的接受状态,则接受空语言。如果你能证明这两个AB和BA都是空的,你已经表明,A = B.
Edit
嘿,我不能相信没有人注意到巨大的错误 - 故意之一,当然: - p
如上所述的自动机AB将接受那些其前半部分被A接受并且后半部分不被B接受的字符串。构建期望的 AB是稍微复杂的过程。我不能把它想成我的头顶,但我确实知道它是明确的(并且可能涉及创建状态来表示接受A的状态和B中的非接受状态的产物)。
2
这真的取决于你的意思是正则表达式。正如其他海报所指出的那样,将这两种表达方式都缩减为最小DFA应该可行,但它仅适用于纯正则表达式。
真实世界中使用的一些结构正则表达式库(特别是反向引用)使它们有能力表达不规则的语言,所以DFA算法不适用于它们。例如,正则表达式:([a-z]*) \1
匹配由空格(a a
和b b
但不是b a
或a b
)分隔的相同单词的双重出现。这完全不能被有限自动机识别。
通过比较两个DFA,你是什么意思?图同构? – damned 2014-01-02 04:40:06
由于你有一个初始状态,并且转换被标记并且是确定性的,所以很容易检查DFA是否相等,比图同构要容易得多。一次深度优先遍历就足够了。 – starblue 2014-01-03 13:35:08