Nondeterministic finite automaton: Difference between revisions

Revision as of 11:30, 14 February 2025

Latest revision as of 08:59, 25 August 2025

(2 intermediate revisions by 2 users not shown)

Line 249:

* 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 journalbook |last1=Meyer |first1=A. R. |last2=Stockmeyer |first2=L. J. |datetitle=13th Annual Symposium on Switching and Automata Theory (Swat 1972-10-25) |titlechapter=The equivalence problem for regular expressions with squaring requires exponential space |journaldate=Proceedings of the 13th Annual Symposium on Switching and Automata Theory (SWAT)1972-10-25 |___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|url-access=subscription }}</ref>

==Application of NFA==

Line 274:

{{DEFAULTSORT:Nondeterministic Finite-State Machine}}

[[Category:Finite-state automatamachines]]