Nondeterministic finite automaton: Difference between revisions

Revision as of 23:38, 12 December 2023

Revision as of 00:44, 13 December 2023

Line 246:

* One can check in linear time whether the language of a given NFA is empty, simply by performing a [[depth-first search]] from the initial state and checking 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 reductionsreduction]]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>

==Application of NFA==