Content deleted Content added
MikaelMonet (talk | contribs) Added a section complexity, move the result that universality is PSPACE complete there (it had nothing to do in "implementation"), added the comlexity of other standart problems |
MikaelMonet (talk | contribs) |
||
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 reductions) 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==
| |||