Editing Nondeterministic finite automaton (section)

== Complexity ==

* One can solve in linear time the [[emptiness problem]] for NFA, i.e., check whether the language of a given NFA is empty. To do this, we can simply perform a [[depth-first search]] from the initial state and check if some final state can be reached.
* It is [[PSPACE]]-complete to test, given an NFA, whether it is ''universal'', i.e., if there is a string that it does not accept.<ref>Historically shown in: {{Cite journal |last1=Meyer |first1=A. R. |last2=Stockmeyer |first2=L. J. |date=1972-10-25 |title=The equivalence problem for regular expressions with squaring requires exponential space |journal=Proceedings of the 13th Annual Symposium on Switching and Automata Theory (SWAT) |location=USA |publisher=IEEE Computer Society |pages=125–129 |doi=10.1109/SWAT.1972.29}} For a modern presentation, see [http://www.lsv.fr/~jacomme/1718/ca/td4_sol.pdf]</ref> As a consequence, the same is true of the ''inclusion problem'', i.e., given two NFAs, is the language of one a subset of the language of the other.
* Given as input an NFA ''A'' and an integer n, the [[counting problem (complexity)|counting problem]] of determining how many words of length ''n'' are accepted by ''A'' is intractable; it is [[♯P|'''#P'''-hard]]. In fact, this problem is complete (under [[parsimonious reduction]]s) for the complexity class [[SpanL]].<ref>{{Cite journal |last1=Álvarez |first1=Carme |last2=Jenner |first2=Birgit |date=1993-01-04 |title=A very hard log-space counting class |url=https://dx.doi.org/10.1016/0304-3975%2893%2990252-O |journal=Theoretical Computer Science |volume=107 |issue=1 |pages=3–30 |doi=10.1016/0304-3975(93)90252-O |issn=0304-3975}}</ref>