我想用一个（简化的）例子来解释我的问题。
正则表达式 1：
^\d+_[a-z]+$
正则表达式 2：
^\d*$
正则表达式1不会匹配正则表达式2匹配的字符串。因此，我们可以说正则表达式1是与正则表达式2正交的。
由于许多人询问我所说的“正交”的含义，我将尝试澄清：
令S1成为正则表达式1匹配的（无限）字符串集合。S2是正则表达式2匹配的字符串集合。如果S1和S2的交集为空，则正则表达式2与正则表达式1正交。例如，正则表达式'^\d_a$'不是正交的，因为字符串'2_a'在集合S1和S2中。
如何确定两个正则表达式是否正交？
最好的情况是使用一些库来实现像下面这样的方法：
/**
* @return True if the regex is orthogonal (i.e. "intersection is empty"), False otherwise or Null if it can't be determined
*/
public Boolean isRegexOrthogonal(Pattern regex1, Pattern regex2);
“Orthogonal”是指“交集为空集”，对吗？
我会构建正则表达式来表示交集，然后将其转换为正常形式的正则文法，并查看它是否是空语言...
不过，我是一个理论家...
这个问题已经发布两年了，但是我很高兴地告诉大家，现在可以通过调用“genex”程序来确定。这里是程序链接：https://github.com/audreyt/regex-genex
$ ./binaries/osx/genex '^\d+_[a-z]+$' '^\d*$'
$
$ runghc Main.hs '\d' '[123abc]'
1.00000000 "2"
1.00000000 "3"
1.00000000 "1"
genex '710/([a-z]){4,8}/.*.jpg' '710.{4,10}'希望能有所帮助！ - audreyt^1(11)*$和^(11)*$？ - Kendall Hopkins关于 \1、\2 的优秀观点…这是无上下文的，所以不可解决。小问题：并非所有东西都可以归约到 Halt…例如程序等价性。- Brian Postow
[我在回复评论]
IIRC, a^n b^m a^n b^m 不是无上下文的，因此 (a\*)(b\*)\1\2 也不是，因为它们是相同的。如果 L 是“好”的语言之一，对于“好”是指 regular、context-free 中的一个，则 ISTR { ww | w ∈ L } 也不是“好”的。
我修改了我的说法：RE 中的一切都可以归约到停机问题;-)
我终于找到了我一直在寻找的库：
用法：
/**
* @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();
}
需要注意的是，此实现不支持复杂的正则表达式功能，如反向引用。请参阅博客文章"A Faster Java Regex Package"，介绍了dk.brics.automaton。
将每个正则表达式转换为DFA。从一个DFA的接受状态创建一个epsilon转换到第二个DFA的起始状态。通过添加epsilon转换，您实际上已经创建了一个NFA。然后将NFA转换为DFA。如果起始状态不是接受状态，并且可以到达接受状态，则两个正则表达式不是“正交”的。（因为它们的交集不为空）。
有已知的程序可将正则表达式转换为DFA，并将NFA转换为DFA。您可以查看像Sipser的《计算理论导论》这样的书籍以获取程序，或者在网络上搜索。毫无疑问，许多本科生和研究生必须在某个“理论”课程中完成此操作。
证明一个正则表达式与另一个正则表达式正交有时可能很简单，例如在相同位置的互斥字符组中。但对于除了最简单的正则表达式之外的任何表达式，这都是一个非平凡的问题。对于包含组和反向引用的复杂表达式，我甚至可以说这可能是不可能的。
我相信kdgregory是正确的，你使用Orthogonal来表示Complement。
这个理解正确吗？