正则表达式:确定两个正则表达式是否可以匹配相同的输入？

Question

我想知道两个已知的正则表达式之间是否存在冲突,以便允许用户构造互斥的正则表达式列表.

例如,我们知道下面的正则表达式是完全不同的,但它们都匹配xy50:

'^xy1\d'
'[^\d]\d2$'

是否有可能使用计算机算法确定两个正则表达式是否会发生冲突？怎么样？

Answer 1

这里没有停顿问题.所有你需要的是计算在路口^xy1\d和[^\d]\d2$非空.

我不能在这里给你一个算法,但这里有两个关于生成交集的方法的讨论,而不是求助于构造DFA:

然后是RAGEL

它也可以计算正则表达式的交集.

更新:我刚用OP的regexp尝试了Ragel.Ragel可以从生成的状态机生成graphviz的"点"文件,这非常棒.OP的regexp的交集在Ragel语法中看起来像这样:

('xy1' digit any*) & (any* ^digit digit '2')

并具有以下状态机:

空路口:

('xy1' digit any*) & ('q' any* ^digit digit '2')

看起来像这样:

因此,如果所有其他方法都失败了,那么您仍然可以通过比较生成的"点"文件来让Ragel计算交集并检查它是否输出空状态机.

Answer 2

问题可以重申为"两个或多个正则表达式描述的语言是否具有非空交集"？

如果您将问题限制在纯正则表达式(没有后向引用,前瞻,后瞻或其他允许识别无上下文或更复杂语言的功能),问题至少是可判定的.常规语言在交集下是封闭的,并且有一种算法将两个正则表达式作为输入,并在有限时间内生成识别交集的DFA.

每个正则表达式可以转换为非确定性有限自动机,然后转换为确定性有限自动机.可以将一对DFA转换为识别交叉点的DFA.如果存在从开始状态到最终DFA的任何接受状态的路径,则交集非空("冲突",使用您的术语).

不幸的是,在将初始NFA转换为DFA时可能存在指数性爆发,因此随着输入表达式的大小增加,问题在实践中很快变得不可行.

如果允许对纯正则表达式进行扩展,则所有投注都将关闭 - 此类语言不再在交叉点下关闭,因此这种结构不起作用.