是否有有效的算法来判断一个NFA接受的语言是否是另一个NFA接受的语言的超集？

Question

给定两个非确定性有限自动机M1和M2，是否有一个有效的算法来确定M1所接受的语言是否是M2接受的语言的超集？

Answer 1

除非P=NP。如果您有这样的算法，您可以很小地判断两个NFA是否是同构的(只要检查A是B的超集，B是A的超集)，这是一个已知NP-困难问题。欲了解更多细节，请访问读这篇论文。它有一个令人沮丧的复杂结果表。