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 - |
Frage
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?
Lösung
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.
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow