Content deleted Content added
Undid revision 1176521915 by 60.243.180.50 (talk): implementations are usually based on DFAs, not NFAs, since the former are more efficient |
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 |
||
Line 241:
* Create multiple copies. For each ''n'' way decision, the NFA creates up to ''n''−1 copies of the machine. Each will enter a separate state. If, upon consuming the last input symbol, at least one copy of the NFA is in the accepting state, the NFA will accept. (This, too, requires linear storage with respect to the number of NFA states, as there can be one machine for every NFA state.)
* Explicitly propagate tokens through the transition structure of the NFA and match whenever a token reaches the final state. This is sometimes useful when the NFA should encode additional context about the events that triggered the transition. (For an implementation that uses this technique to keep track of object references have a look at Tracematches.)<ref>Allan, C., Avgustinov, P., Christensen, A. S., Hendren, L., Kuzins, S., Lhoták, O., de Moor, O., Sereni, D., Sittampalam, G., and Tibble, J. 2005. [http://abc.comlab.ox.ac.uk/papers#oopsla2005 Adding trace matching with free variables to AspectJ] {{Webarchive|url=https://web.archive.org/web/20090918053718/http://abc.comlab.ox.ac.uk/papers#oopsla2005 |date=2009-09-18 }}. In Proceedings of the 20th Annual ACM SIGPLAN Conference on Object Oriented Programming, Systems, Languages, and Applications (San Diego, CA, USA, October 16–20, 2005). OOPSLA '05. ACM, New York, NY, 345-364.</ref>
* 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.▼
== Complexity ==
* 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 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==
| |||