算法：二正则表达式

Question

我想弄清楚（在运行时）两个正则表达式是否交叉的路口（即如果他们这样做存在一个或多个字符串比赛双方正则表达式）。

算法必须非常快，我需要遍历数据库，检查现有值。

在这方面找到了一些理论，但没有实现？

Answer 1

明显的解决方案是将正则表达式转换成有限自动机，计算的DFA（简单）的交叉点，看看是否有什么产生的DFA可以接受（也微不足道）。唯一困难的部分是将正则表达式转换为DFA，这需要一些工作。

Answer 2

使用正则表达式的偏导数下面是一个implementation in Haskell。对这篇文章的评论指出了克里斯多德的答案中的一个问题。

Answer 3

怎么样检查第一个，然后通过第一个输入的输入？