我正在寻找功能（PHP将是最好的），无论是否存在字符串匹配regexpA和regexpB，它都返回true。
例1：
$regexpA = '[0-9]+';
$regexpB = '[0-9]{2,3}';
hasRegularsIntersection($regexpA,$regexpB) 因为返回TRUE '12' 匹配两个正则表达式
例2：
$regexpA = '[0-9]+';
$regexpB = '[a-z]+';
hasRegularsIntersection($regexpA,$regexpB) 返回FALSE，因为数字永远不会与文字匹配。
感谢您提出如何解决此问题的任何建议。
亨利
对于实际上是常规的正则表达式（即不使用后向引用等不规则的功能），您可以执行以下操作：
用法：
/**
* @return true if the two regexes will never both match a given string
*/
public boolean isRegexOrthogonal( String regex1, String regex2 ) {
Automaton automaton1 = new RegExp(regex1).toAutomaton();
Automaton automaton2 = new RegExp(regex2).toAutomaton();
return automaton1.intersection(automaton2).isEmpty();
}
正则表达式指定可以识别可能无限的字符串集的有限状态机。字符串集可以是无限的，但状态数必须是有限的，因此您可以逐个检查状态。
以你的第二个例子为例：在第一个表达式中，要从状态0到状态1，字符串必须以数字开头。在第二个表达式中，要从状态0到状态1，字符串必须以字母开头。所以你知道在BOTH表达式中没有字符串可以让你从状态0到状态1。你有答案。
以第一个例子为例：你知道如果字符串以数字开头，你可以用正则表达式从状态0到状态1。所以现在你可以为每个消除状态0，并且只回答两个（现在是一个小的状态）有限状态机中的每一个的问题。
这看起来很像众所周知的“暂停问题”，正如你所知，对于图灵机或同等机器而言，这是一个无法解决的问题。但实际上停止问题对于有限状态机是可解的，仅仅因为存在有限数量的状态。
我相信你可以用一个非确定性的FSM来解决这个问题。如果你的正则表达式只有一个从每个状态到下一个状态的转换，那么确定性的FSM可以解决它。但正则表达式意味着，例如，如果你处于状态2，那么如果caracter是一个数字，你将进入状态3，否则如果该字符是一个字母，你将进入状态4。
所以这就是我要做的：
解决它只能从一个状态到下一个状态的一个FSM的子集。例如，匹配“Bob”和“bob”的正则表达式，以及仅匹配“bob”和“boB”的第二个正则表达式。
看看您是否可以在有限状态机中实现该解决方案。我认为这应该是可能的。状态的输入是表示一个FSM的转换和第二个FSM的转换的对。例如：状态0：如果（r1，r2）是（（“B”或“b”），“b”）则状态1.状态1：如果（r1，r2）是（（“o”），（ “o”））然后状态2.等
现在对于更一般的情况，例如状态二返回到状态二或更早的状态;例如，正则表达式1仅识别“会面”，但正则表达式2识别具有无限数量的e的“meeeet”。你必须将它们减少到正则表达式1识别“t”和正则表达式2识别“t”。我认为这可能是由非确定性FSM解决的。
无论如何，那是我的直觉。
我不认为它是NP完全的，只是因为我的直觉告诉我你应该能够通过每个步骤缩短每个正则表达式。
有可能的。在学习语义Web技术时，我曾经使用Pellet OWL推理器遇到过它。
这是一个例子 这表明如何将正则表达式解析为树结构。然后，您可以（理论上）将您的两个正则表达式解析为树，并查看一棵树是否是另一棵树的子集，即。如果在其他树的节点中可以找到一棵树。
如果找到，那么另一个正则表达式将匹配（不仅仅是）第一个正则表达式匹配的子集。
这不是一个解决方案，但也许它会帮助你。