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

Question

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

Answer 1

除非 P=NP。如果您有这样的算法，您可以轻松地确定两个 NFA 是否同构（只需检查 A 是否是 B 的超集，B 是否是 A 的超集），这是一个已知的 NP 难题。有关详细信息，请阅读本文。它有一个令人沮丧的复杂结果表。