Is there an efficient algorithm to decide whether the language accepted by one NFA is a superset of the language accepted by another?
-
12-11-2019 - |
Question
Given two nondeterministic finite automata M1 and M2, is there an efficient algorithm to determine whether the language accepted by M1 is a superset of the language accepted by M2?
Solution
Not unless P=NP. If you had such an algorithm, you could trivially decide whether two NFAs were isomorphic (just check if A is a superset of B and B is a superset of A), which is a known NP-hard problem. For more details, read this paper. It has a nice discouraging table of complexity results.
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow