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

Question

我想找出两个已知的正则表达式之间是否可能存在冲突，以便允许用户构造一个互斥的正则表达式列表。

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

'^xy1\d'

'[^\d]\d2$'

是否可以使用计算机算法确定两个正则表达式是否存在这种冲突？怎么样？

Answer 1

问题可以用“两个或多个正则表达式描述的语言是否具有非空交集”来重新描述吗？如果将问题限制为纯正则表达式（没有反向引用，超前，向后查找或其他允许识别上下文无关或更复杂语言的功能），则该问题至少是可确定的。规则语言在交集下是封闭的，并且有一种算法将这两个正则表达式作为输入并在有限时间内生成可识别交集的DFA。每个正则表达式可以转换为不确定的有限自动机，然后转换为确定的有限自动机。可以将一对DFA转换为可识别相交的DFA。如果存在从开始状态到最终DFA的任何接受状态的路径，则交集为非空（使用您的术语来说是“冲突”）。不幸的是，当将初始NFA转换为DFA时，可能会出现指数爆炸，因此，随着输入表达式大小的增加，该问题在实践中很快变得不可行。而且，如果允许对纯正则表达式进行扩展，那么所有的赌注都将失效-此类语言将不再在交集下关闭，因此该构造将无法正常工作。