Cheap and Secure Web Hosting Provider : See Now

Does a given e-NFA accepts all the Strings?

, , No Comments
Problem Detail: 

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.

Asked By : TheoryQuest1
Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/61113

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback