是否有一种有效的算法来决定一个NFA接受的语言是否是另一个NFA接受的语言的超集？

Question

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

Answer 1

除非 P=NP。如果你有这样的算法，你可以简单地判断两个 NFA 是否同构（只需检查 A 是否是 B 的超集，B 是否是 A 的超集），这是一个已知的 NP 难问题。有关更多详细信息，请阅读本文。它有一个很好的令人沮丧的复杂性结果表。