1
$\begingroup$

Given an e-NFA. It is easy to find a string that is accepted by it. But, how do we find if the given e-NFA accepts "All" the strings over the alphabet. Or if there is a string that is not accepted by it.

Of course the usual way is to construct a DFA, or complement the e-NFA but since we are talking about the whole language, I was wondering if there is a much more efficent method in the worst case.

$\endgroup$
2
$\begingroup$

A classical result, attributed to Meyer and Stockmeyer, is that checking whether an NFA accepts all strings is PSPACE-complete. Nevertheless, there are some non-trivial heuristic algorithms. See for example Antichains: A New Algorithm for Checking Universality of Finite Automata by De Wulf, Doyen, Henzinger and Raskin.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.