Does a given e-NFA accepts all the Strings?

6/8/2025 2:46:59 AM
Questions › Does a given e-NFA accepts all the Strings?
-1 Vote Up Vote Down
AnonymousPublished on: 6/8/2025 2:46:59 AM
Does a given e-NFA accepts all the Strings?

1 Answers
Best Answer 2
admin 5/3/2018 1:43:00 PM

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