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.
Does a given e-NFA accepts all the Strings?
regular languages;finite automata;regular expressions
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.