互斥正则表达式

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

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

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

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

2010-06-03 captncraig

可能的重复[如何检测两个正则表达式是否可以匹配字符串重叠？]（http://stackoverflow.com/questions/1849447/how-can-you-detect-if-two-regular - 表达 - 重叠在字符串，他们可以垫） – 2010-06-03 17:01:33

我想我误解了。你的意思是两个给定的正则表达式必须完全相互排斥*任何*输入字符串？也就是说，2^32个可能的四字节字符串，正则表达式只能匹配一种可能性？是不是像说：匹配这个确切的字符串？ – Abel 2010-06-03 17:23:13

我的意思是正则表达式的交集必须为零。没有字符串匹配超过1个正则表达式。 – captncraig 2010-06-03 17:25:28

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

这个问题是，通常的正则表达式 - > DFA算法的第一步是将正则表达式转换为NFA，然后将NFA转换为DFA。但是最后一步会导致DFA状态数量出现指数式放大，所以对于非常简单的正则表达式，这只能是。

如果您使用的是扩展正则表达式语法，则所有投注均为关闭：上下文无关语言在交集之下未关闭，因此此方法不起作用。

来源

2010-06-03 17:10:14

有趣的想法。我认为你正在与Jeffrey Friedl交手，他说（第157页）“谈论DFA匹配非常无聊”。您只是再次感兴趣（接受DFA仍然极力限制您）！ – Abel 2010-06-03 17:17:50

那就是我所害怕的。尽管非常有趣的答案。 – captncraig 2010-06-03 17:52:18

的Wkipedia article on regular expressions确实状态

是可能的写的算法对于两个给定正则表达式决定所描述的语言是否基本相等，减小了每个表达式的最小确定性有限状态机，并判断它们是否是同构的（等价的）。

但没有提供进一步的提示。

当然，以后的简单方法是进行大量测试 - 但我们都知道测试作为一种证明方法的缺点。

来源

2010-06-03 16:56:36

我相信CaptnCraig想知道这些语言是否有非空的交集，而不是它们是否相同。 – 2010-06-03 17:15:45

你不能这样做只看正则表达式。

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

重点是正则表达式不够信息。结果取决于正则表达式和目标字符串。

来源

2010-06-03 16:57:12 Seth

*“当应用于字符串”11“时，它们会产生不同的结果。”*实际上：它们不会，它们会产生相同的结果。除非你添加锚定。 – Abel 2010-06-03 17:00:14

对于纯正则表达式，CaptnCraig要求的是可能的（但可能效率低下）。他想知道两个常规语言（由正则表达式指定）是否具有非空的相交。对于你的例子，答案是“是”。 – 2010-06-03 17:02:11

@Abel：我想他的意思是他们匹配的字符串的部分是不同的。他们都会匹配。 – 2010-06-03 17:02:25

互斥正则表达式

回答

相关问题