正则表达式“包含”另一个正则表达式

Question

有没有方法可以测试正则表达式是否包含另一个正则表达式？
例如：

RegEX1 = "a.*b"; 
RegEx2 = "a1.*b"; 

regex1的 “包含” RegEX2。

据我所知 - 这是做不到的，我错了吗？

---

好的，joel.neely已经表明它可以在学术上完成（还没有读过......）。

可以用C＃编程语言来完成吗？
那会有多有效？测试1000对需要多长时间？

Answer 1

是的。

This paper包含有关该主题的详细讨论（请参阅第4.4节）。

Answer 2

将两个表达式转换为等价的状态机，并检查两台机器中的所有路径是否允许相同的匹配，应该有所斩断。抽水马克应该很明显，所以避免重新访问旧节点。

它只适用于“简单”正则表达式（或真实的，你有什么，perls递归表达式更富有表现力）。

虽然状态机的图形可能有大量的路径，但它仍应该受到限制（尤其是表达式的来源是人为的）。因此，您可以找到RegEX1的所有允许路径，然后逐个检查RegEX2中是否允许。如果所有路径都是有效的，你就会知道那个路径包含在另一个路径中。