有明确定义的办法 基本上是 nfa->dfa 然后从两个 dfa 生成一个补集的交集 然后判断这个交集是否存在任何合法输入： a = dfa(e1) ^ ~(dfa(e2)).
写作业的话难度不算太大，两三个人小组做一个月应该出来了。但是要做一个工业上实用的实现，难度比较大，因为这明显是一个 pspace 复杂度的问题，因为 nfa->dfa 的缘故。如果是想挑战自己一下，可以试试看。
这方面的知识其实不难，不过因为是非常老的话题，论文和书都比较干涩，而且有一些folklore的知识点，要捡起来还是得花不少功夫。
--
FROM 188.67.171.*