regex - 互斥正则表达式

Question

如果我有一个正则表达式列表，是否有一种简单的方法可以确定它们中的任何一个都不会返回相同字符串的匹配项？

也就是说，当且仅当对于所有字符串，列表中最多有一项与整个字符串匹配时，该列表才有效。

看起来这将很难（也许不可能？）明确地证明，但我似乎找不到任何关于这个主题的工作。

我问的原因是我正在研究一个接受正则表达式的标记器，我想确保一次只有一个标记可以匹配输入的头部。

Answer 1

如果您使用的是纯正则表达式（没有反向引用或其他导致它们识别无上下文或更复杂语言的功能），您所问的都是可能的。您可以做的是将每个正则表达式转换为 DFA，然后（因为常规语言在交集下关闭）将它们组合成一个识别两种语言交集的 DFA。如果该 DFA 具有从开始状态到接受状态的路径，则两个输入正则表达式都接受该字符串。

这样做的问题是，通常的 regex->DFA 算法的第一步是将 regex 转换为 NFA，然后将 NFA 转换为 DFA。但是最后一步可能会导致 DFA 状态的数量呈指数级增长，因此这仅适用于非常简单的正则表达式。

如果您正在使用扩展的正则表达式语法，那么所有的赌注都是关闭的：上下文无关语言不会在交集下关闭，因此这种方法将不起作用。

Answer 2

维基百科关于正则表达式的文章确实说明了

可以编写一个算法，针对两个给定的正则表达式确定所描述的语言是否本质上相等，将每个表达式简化为最小确定性有限状态机，并确定它们是否同构（等价）。

但没有给出进一步的提示。

当然，您所追求的简单方法是运行大量测试——但我们都知道测试作为证明方法的缺点。

Answer 3

您不能仅通过查看正则表达式来做到这一点。

考虑你有[0-9]和的情况[0-9]+。它们显然是不同的表达式，但是当应用于字符串“1”时，它们都会产生相同的结果。当应用于字符串“11”时，它们会产生不同的结果。

关键是正则表达式没有足够的信息。结果取决于正则表达式和目标字符串。