Nondeterministic finite automaton: Difference between revisions

Revision as of 00:44, 13 December 2023

Revision as of 01:26, 13 December 2023

Line 244:

== Complexity ==

* One can checksolve in linear time the [[emptiness problem]] for NFA, i.e., check whether the language of a given NFA is empty. To do this, simplywe bycan simply performingperform a [[depth-first search]] from the initial state and checkingcheck 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 |last=Meyer |first=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> 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.

* It is [[♯P|'''#P'''-hard]], given as input an NFA ''A'' and an integer n, to determine the number of words of length ''n'' that are accepted by ''A''. In fact, this problem is complete (under [[parsimonious reduction]]s) for the complexity class [[SpanL]].<ref>{{Cite journal |last=Álvarez |first=Carme |last2=Jenner |first2=Birgit |date=1993-01-04 |title=A very hard log-space counting class |url=https://www.sciencedirect.com/science/article/pii/030439759390252O |journal=Theoretical Computer Science |volume=107 |issue=1 |pages=3–30 |doi=10.1016/0304-3975(93)90252-O |issn=0304-3975}}</ref>