Content deleted Content added
→Informal introduction: update ref to 3rd ed (using {sfn}) |
m update 3rd ed refs |
||
Line 49:
*# <math>\delta^*(r, \epsilon) = \{r\}</math> where <math>\epsilon</math> is the empty string, and
*# <math>\delta^*(r, xa)= \bigcup_{r' \in \delta^*(r, x)} \delta(r', a)</math> for all <math>x \in \Sigma^*, a \in \Sigma</math>.
:In words, <math>\delta^*(r, x)</math> is the set of all states reachable from state <math>r</math> by consuming the string <math>x</math>. The string <math>w</math> is accepted if some accepting state in <math>F</math> can be reached from the start state <math>q_0</math> by consuming <math>w</math>.<ref name="Hopcroft.Ullman.1979"/>{{rp|21}}
===Initial state===
Line 238:
There are many ways to implement a NFA:
* Convert to the equivalent DFA. In some cases this may cause exponential blowup in the number of states.<ref>{{cite web|url=https://cseweb.ucsd.edu//~ccalabro/essays/fsa.pdf|title=NFA to DFA blowup|website=cseweb.ucsd.edu|date=February 27, 2005|access-date=6 March 2023|author=Chris Calabro}}</ref>
* Keep a [[set data structure]] of all states which the NFA might currently be in. On the consumption of an input symbol, [[set union|unite]] the results of the transition function applied to all current states to get the set of next states; if ε-moves are allowed, include all states reachable by such a move (ε-closure). Each step requires at most ''s''<sup>2</sup> computations, where ''s'' is the number of states of the NFA. On the consumption of the last input symbol, if one of the current states is a final state, the machine accepts the string. A string of length ''n'' can be processed in time [[Big O notation#Formal definition|''O'']](''ns''<sup>2</sup>),
* 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>
| |||