Nondeterministic finite automaton: Difference between revisions

Revision as of 08:39, 7 March 2023

Revision as of 22:01, 11 April 2023

Line 7:

Using the [[subset construction algorithm]], each NFA can be translated to an equivalent DFA; i.e., a DFA recognizing the same [[formal language]].<ref>{{cite book |title=Introduction to Languages and the Theory of Computation |last1=Martin |first1=John |year=2010 |page=108 |publisher=McGraw Hill |isbn= 978-0071289429}}</ref>

Like DFAs, NFAs only recognize [[regular languageslanguage]]s.

NFAs were introduced in 1959 by [[Michael O. Rabin]] and [[Dana Scott]],<ref>{{cite journal |doi=10.1147/rd.32.0114 |last=Rabin |first=M. O. |last2=Scott |first2=D. |title=Finite Automata and Their Decision Problems |journal=IBM Journal of Research and Development |volume=3 |issue=2 |pages=114–125 |date=April 1959 }}</ref> who also showed their equivalence to DFAs. NFAs are used in the implementation of [[regular expression]]s: [[Thompson's construction]] is an algorithm for compiling a regular expression to an NFA that can efficiently perform pattern matching on strings. Conversely, [[Kleene's algorithm]] can be used to convert an NFA into a regular expression (whose size is generally exponential in the input automaton).

Line 23:

==Formal definition==

For a more elementary introduction of the formal definition, see [[automata theory]].

===Automaton===

An ''NFA'' is represented formally by a 5-[[n-tuple|5-tuple]],

<math>(Q, \Sigma, \delta, q_0, F)</math>, consisting of

* a finite [[Set (mathematics)|set]] of states <math>Q</math>.

Line 65:

Let <math>M = (\{p, q\}, \{0, 1\}, \delta, p, \{q\})</math> where

the transition function <math>\delta</math> can be defined by this [[state transition table]] (cf. upper left picture):

:{| class="wikitable" style="text-align:center;"

! {{diagonal split header|State|Input}}

! 0

Line 108:

Conversely, for each NFA, there is a DFA such that it recognizes the same formal language. The DFA can be constructed using the [[powerset construction]].

This result shows that NFAs, despite their additional flexibility, are unable to recognize languages that cannot be recognized by some DFA. It is also important in practice for converting easier-to-construct NFAs into more efficiently executable DFAs. However, if the NFA has ''n'' states, the resulting DFA may have up to 2<mathsup>2^{''n}''</mathsup> states, which sometimes makes the construction impractical for large NFAs.

==NFA with ε-moves==

Line 115:

===Formal definition===

An ''NFA-ε'' is represented formally by a 5-[[n-tuple|5-tuple]], <math>(Q, \Sigma, \delta, q_0, F)</math>, consisting of

* a finite [[Set (mathematics)|set]] of [[State (computer science)|states]] <math>Q</math>

* a finite set of [[input symbol]]s called the [[Alphabet (computer science)|alphabet]] <math>\Sigma</math>

Line 122:

* a set of states <math>F</math> distinguished as [[Finite-state machine#Accept .28or final.29 states|''accepting'' (or ''final'') ''states'']] <math>F \subseteq Q</math>.

Here, <math>\mathcal{P}(Q)</math> denotes the [[power set]] of <math>Q</math> and ε<math>\epsilon</math> denotes empty string.

===ε-closure of a state or set of states===

Line 203:

By construction, <math>M'</math> has no ε-transitions.

One can prove that <math>\delta'^*(q_0,w) = \delta^*(q_0,w)</math> for each string <math>w \neq \varepsilon</math>, by [[mathematical induction|induction]] on the length of <math>w .</math>

Based on this, one can show that <math>\delta'^*(q_0,w) \cap F' \neq \{\}</math> if, and only if, <math>\delta^*(q_0,w) \cap F \neq \{\} ,</math> for each string <math>w \in \Sigma^* :</math>

* If <math>w = \varepsilon ,</math> this follows from the definition of <math>F' .</math>

* Otherwise, let <math>w = va</math> with <math>v \in \Sigma^*</math> and <math>a \in \Sigma .</math>

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''² 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''²),<ref name="Hopcroft.Motwani.Ullman.2003"/>{{rp|153}} and space ''O''(''s'').

* Create multiple copies. For each ''n'' way decision, the NFA creates up to <math>''n-1</math>''−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.