Jon*_*ehl 33
没有简单的方法.
只要您的正则表达式仅使用标准功能(Perl允许您在匹配中嵌入任意代码,我认为),您可以从每个产生一个非确定性有限状态自动机(NFA),它紧凑地编码RE匹配的所有字符串.
给定任何一对NFA,它们的交集是否为空是可判定的.如果交集不为空,则某些字符串匹配该对中的两个RE(反之).
标准的可判定性证明是首先将它们确定为DFA,然后构造一个新的DFA,其状态是两个DFA状态的对,并且其最终状态正是该对中的两个状态在其原始DFA中最终的状态. .或者,如果您已经展示了如何计算NFA的补充,那么您可以(DeMorgan的法律风格)得到交叉点complement(union(complement(A),complement(B))).
不幸的是,NFA-> DFA涉及潜在的指数大小爆炸(因为DFA中的状态是NFA中的状态子集).来自维基百科:
某些常规语言类只能通过确定性有限自动机来描述,其大小以最短等效正则表达式的大小呈指数增长.标准示例在这里是由字母{a,b}上的所有字符串组成的语言L_k,其第k个字母等于a.
顺便说一下,你绝对应该使用OpenFST.您可以将自动机创建为文本文件,并使用最小化,交叉等操作来查看它们对您的问题的效率.已经存在开源的regexp-> nfa-> dfa编译器(我记得有一个Perl模块); 修改一个输出OpenFST自动机文件并播放.
幸运的是,可以避免状态子集爆炸,并使用与DFA相同的结构直接交叉两个NFA:
如果A ->a B (在一个NFA中,你可以从状态A到B输出字母'a')
和X ->a Y(在另一个NFA中)
然后(A,X) ->a (B,Y)在十字路口
(C,Z) 是最终的iff C在一个NFA中是最终的而Z在另一个中是最终的.
要开始关闭过程,您将从两个NFA的开始状态对开始,例如(A,X)- 这是交叉点NFA的开始状态.每次第一次访问状态时,按照上述规则为离开这两个状态的每对弧生成一个弧,然后访问这些弧到达的所有(新)状态.您将存储扩展状态弧的事实(例如,在哈希表中)并最终探索从一开始就可以到达的所有状态.
如果你允许epsilon过渡(不输出字母),那很好:
如果A ->epsilon B在第一个NFA中,那么对于(A,Y)您到达的每个州,添加弧(A,Y) ->epsilon (B,Y),对于第二个位置NFA中的epsilons也是如此.
在将正则表达式转换为NFA时,Epsilon转换对于获取两个NFA的并集是有用的(但不是必需的); 无论何时进行交替regexp1|regexp2|regexp3,你都可以使用并集:一个NFA,它的起始状态有一个epsilon转换到每个代表交替中的regexp的NFA.
确定NFA的空虚很容易:如果你从开始状态进行深度优先搜索时达到最终状态,那么它就不是空的.
该NFA交叉类似于有限状态换能器组成(换能器是输出符号对的NFA,它们成对连接以匹配输入和输出串,或者将给定输入转换为输出).