algorithm - 有没有办法检查两个正则表达式是否可以匹配相同的字符串？

Question

我有两个正则表达式。我需要确定是否可以同时构建与这两个正则表达式匹配的给定长度的字符串。我需要算法来做到这一点。

字符串的长度不会超过 20 个字符。

Answer 1

这取决于。对于 perl 兼容的正则表达式 (pcre)，这通常是不可能的，因为它们已经完成了：您甚至无法确定匹配总是终止。

对于乔姆斯基层次结构中定义的原始“干净”形式的正则语言，已知它们在交集下是封闭的，这已经在这个线程中讨论过。

一旦你有了交叉点的NFA，就很容易检查是否有任何字符串匹配它 - 如果 thera 是从你的 NFA 开始到结束的路径，那么这个路径的字符串就是你正在搜索的字符串，对于DFAs，这里给出了一个算法，应该很简单的让它适应NFAs。