cap*_*aig 10 regex mutual-exclusion
如果我有一个正则表达式列表,是否有一种简单的方法可以确定它们中没有两个都会返回相同字符串的匹配项？
也就是说,列表是有效的,当且仅当对于所有字符串,列表中最多一个项目将匹配整个字符串.
似乎这将是非常困难的(可能不可能？)来明确证明,但我似乎无法找到关于这个主题的任何工作.
我问的原因是我正在处理一个接受正则表达式的标记化器,我想确保一次只有一个标记可以匹配输入的头部.
如果您正在使用纯正则表达式(没有后向引用或其他功能导致它们识别无上下文或更复杂的语言),您可以提出的问题.您可以做的是将每个正则表达式转换为DFA,然后(因为常规语言在交叉点下关闭)将它们组合成一个识别两种语言交集的DFA.如果该DFA具有从开始状态到接受状态的路径,则该输入regexen都接受该字符串.
这个问题是通常的正则表达式 - > DFA算法的第一步是将正则表达式转换为NFA,然后将NFA转换为DFA.但是最后一步可能会导致DFA状态数量呈指数式增长,因此这对于非常简单的正则表达式来说是可行的.
如果您正在使用扩展的正则表达式语法,则所有的注意都是关闭的:无交叉语言不会在交集下关闭,因此此方法不起作用.