Nondeterministic finite automaton

<h2 id="informal-introduction">Informal introduction</h2>
There are at least two equivalent ways to describe the behavior of an NFA. The first way makes use of the <a href="/facts/Nondeterministic_algorithm/UubLdp3D">nondeterminism</a> in the name of an NFA. For each input symbol, the NFA transitions to a new state until all input symbols have been consumed. In each step, the automaton nondeterministically "chooses" one of the applicable transitions. If there exists at least one "lucky run", i.e. some sequence of choices leading to an accepting state after completely consuming the input, it is accepted. Otherwise, i.e. if no choice sequence at all can consume all the input<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a> and lead to an accepting state, the input is rejected.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a><a class="footnote-ref" id="fnref:5" href="#fn:5">5</a>: 319 <a class="footnote-ref" id="fnref:6" href="#fn:6">6</a>
In the second way, the NFA consumes a string of input symbols, one by one. In each step, whenever two or more transitions are applicable, it "clones" itself into appropriately many copies, each one following a different transition. If no transition is applicable, the current copy is in a dead end, and it "dies". If, after consuming the complete input, any of the copies is in an accept state, the input is accepted, else, it is rejected.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a><a class="footnote-ref" id="fnref:8" href="#fn:8">8</a><a class="footnote-ref" id="fnref:9" href="#fn:9">9</a>

<h2 id="formal-definition">Formal definition</h2>
For a more elementary introduction of the formal definition, see <a href="/facts/Automata_theory/Q6BmPv63">automata theory</a>.

<h3>Automaton</h3>
An NFA is represented formally by a 5-<a href="/facts/Tuple/BI1HIxL8">tuple</a>,

(
 Q
 ,
 Σ
 ,
 δ
 ,
 
 q
 
 0
 
 
 ,
 F
 )
 
 
 {\displaystyle (Q,\Sigma ,\delta ,q_{0},F)}
 
, consisting of

<ul><li>a finite <a href="/facts/Set_(mathematics)/BfucfHMq">set</a> of <a href="/facts/State_(computer_science)/4Yu8xXHS">states</a> 
 
 
 
 Q
 
 
 {\displaystyle Q}
 
,</li>
<li>a finite set of input symbols called the <a href="/facts/Alphabet_(computer_science)/6KW9qYRW">alphabet</a> 
 
 
 
 Σ
 
 
 {\displaystyle \Sigma }
 
,</li>
<li>a transition <a href="/facts/Function_(mathematics)/CdReEKCh">function</a> 
 
 
 
 δ
 
 
 {\displaystyle \delta }
 
 : 
 
 
 
 Q
 ×
 Σ
 →
 
 
 P
 
 
 (
 Q
 )
 
 
 {\displaystyle Q\times \Sigma \rightarrow {\mathcal {P}}(Q)}
 
,</li>
<li>an initial (or start) state 
 
 
 
 
 q
 
 0
 
 
 ∈
 Q
 
 
 {\displaystyle q_{0}\in Q}
 
, and</li>
<li>a set of accepting (or final) states 
 
 
 
 F
 ⊆
 Q
 
 
 {\displaystyle F\subseteq Q}
 
.</li></ul>
Here, 
 
 
 
 
 
 P
 
 
 (
 Q
 )
 
 
 {\displaystyle {\mathcal {P}}(Q)}
 
 denotes the <a href="/facts/Power_set/FVuf8PDD">power set</a> of 
 
 
 
 Q
 
 
 {\displaystyle Q}
 
.

<h3>Recognized language</h3>
Given an NFA 
 
 
 
 M
 =
 (
 Q
 ,
 Σ
 ,
 δ
 ,
 
 q
 
 0
 
 
 ,
 F
 )
 
 
 {\displaystyle M=(Q,\Sigma ,\delta ,q_{0},F)}
 
, its recognized language is denoted by 
 
 
 
 L
 (
 M
 )
 
 
 {\displaystyle L(M)}
 
, and is defined as the set of all strings over the alphabet 
 
 
 
 Σ
 
 
 {\displaystyle \Sigma }
 
 that are accepted by 
 
 
 
 M
 
 
 {\displaystyle M}
 
.
Loosely corresponding to the above informal explanations, there are several equivalent formal definitions of a string 
 
 
 
 w
 =
 
 a
 
 1
 
 
 
 a
 
 2
 
 
 .
 .
 .
 
 a
 
 n
 
 
 
 
 {\displaystyle w=a_{1}a_{2}...a_{n}}
 
 being accepted by 
 
 
 
 M
 
 
 {\displaystyle M}
 
:

<ul><li>
 
 
 
 w
 
 
 {\displaystyle w}
 
 is accepted if a sequence of states, 
 
 
 
 
 r
 
 0
 
 
 ,
 
 r
 
 1
 
 
 ,
 .
 .
 .
 ,
 
 r
 
 n
 
 
 
 
 {\displaystyle r_{0},r_{1},...,r_{n}}
 
, exists in 
 
 
 
 Q
 
 
 {\displaystyle Q}
 
 such that:
<ol><li>
 
 
 
 
 r
 
 0
 
 
 =
 
 q
 
 0
 
 
 
 
 {\displaystyle r_{0}=q_{0}}
 
</li>
<li>
 
 
 
 
 r
 
 i
 +
 1
 
 
 ∈
 δ
 (
 
 r
 
 i
 
 
 ,
 
 a
 
 i
 +
 1
 
 
 )
 
 
 {\displaystyle r_{i+1}\in \delta (r_{i},a_{i+1})}
 
, for 
 
 
 
 i
 =
 0
 ,
 …
 ,
 n
 −
 1
 
 
 {\displaystyle i=0,\ldots ,n-1}
 
</li>
<li>
 
 
 
 
 r
 
 n
 
 
 ∈
 F
 
 
 {\displaystyle r_{n}\in F}
 
.</li></ol></li></ul>
In words, the first condition says that the machine starts in the start state 
 
 
 
 
 q
 
 0
 
 
 
 
 {\displaystyle q_{0}}
 
. The second condition says that given each character of string 
 
 
 
 w
 
 
 {\displaystyle w}
 
, the machine will transition from state to state according to the transition function 
 
 
 
 δ
 
 
 {\displaystyle \delta }
 
. The last condition says that the machine accepts 
 
 
 
 w
 
 
 {\displaystyle w}
 
 if the last input of 
 
 
 
 w
 
 
 {\displaystyle w}
 
 causes the machine to halt in one of the accepting states. In order for 
 
 
 
 w
 
 
 {\displaystyle w}
 
 to be accepted by 
 
 
 
 M
 
 
 {\displaystyle M}
 
, it is not required that every state sequence ends in an accepting state, it is sufficient if one does. Otherwise, i.e. if it is impossible at all to get from 
 
 
 
 
 q
 
 0
 
 
 
 
 {\displaystyle q_{0}}
 
 to a state from 
 
 
 
 F
 
 
 {\displaystyle F}
 
 by following 
 
 
 
 w
 
 
 {\displaystyle w}
 
, it is said that the automaton rejects the string. The set of strings 
 
 
 
 M
 
 
 {\displaystyle M}
 
 accepts is the <a href="/facts/Formal_language/crDTyP8q">language</a> recognized by 
 
 
 
 M
 
 
 {\displaystyle M}
 
 and this language is denoted by 
 
 
 
 L
 (
 M
 )
 
 
 {\displaystyle L(M)}
 
.<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a>: 320 <a class="footnote-ref" id="fnref:11" href="#fn:11">11</a>
<ul><li>Alternatively, 
 
 
 
 w
 
 
 {\displaystyle w}
 
 is accepted if 
 
 
 
 
 δ
 
 ∗
 
 
 (
 
 q
 
 0
 
 
 ,
 w
 )
 ∩
 F
 ≠
 ∅
 
 
 {\displaystyle \delta ^{*}(q_{0},w)\cap F\not =\emptyset }
 
, where 
 
 
 
 
 δ
 
 ∗
 
 
 :
 Q
 ×
 
 Σ
 
 ∗
 
 
 →
 
 
 P
 
 
 (
 Q
 )
 
 
 {\displaystyle \delta ^{*}:Q\times \Sigma ^{*}\rightarrow {\mathcal {P}}(Q)}
 
 is defined <a href="/facts/Recursion_(computer_science)/2uXo18Gv">recursively</a> by:
<ol><li>
 
 
 
 
 δ
 
 ∗
 
 
 (
 r
 ,
 ϵ
 )
 =
 {
 r
 }
 
 
 {\displaystyle \delta ^{*}(r,\epsilon )=\{r\}}
 
 where 
 
 
 
 ϵ
 
 
 {\displaystyle \epsilon }
 
 is the empty string, and</li>
<li>
 
 
 
 
 δ
 
 ∗
 
 
 (
 r
 ,
 x
 a
 )
 =
 
 ⋃
 
 
 r
 ′
 
 ∈
 
 δ
 
 ∗
 
 
 (
 r
 ,
 x
 )
 
 
 δ
 (
 
 r
 ′
 
 ,
 a
 )
 
 
 {\displaystyle \delta ^{*}(r,xa)=\bigcup _{r'\in \delta ^{*}(r,x)}\delta (r',a)}
 
 for all 
 
 
 
 x
 ∈
 
 Σ
 
 ∗
 
 
 ,
 a
 ∈
 Σ
 
 
 {\displaystyle x\in \Sigma ^{*},a\in \Sigma }
 
.</li></ol></li></ul>
In words, 
 
 
 
 
 δ
 
 ∗
 
 
 (
 r
 ,
 x
 )
 
 
 {\displaystyle \delta ^{*}(r,x)}
 
 is the set of all states reachable from state 
 
 
 
 r
 
 
 {\displaystyle r}
 
 by consuming the string 
 
 
 
 x
 
 
 {\displaystyle x}
 
. The string 
 
 
 
 w
 
 
 {\displaystyle w}
 
 is accepted if some accepting state in 
 
 
 
 F
 
 
 {\displaystyle F}
 
 can be reached from the start state 
 
 
 
 
 q
 
 0
 
 
 
 
 {\displaystyle q_{0}}
 
 by consuming 
 
 
 
 w
 
 
 {\displaystyle w}
 
.<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a><a class="footnote-ref" id="fnref:13" href="#fn:13">13</a>
<h3>Initial state</h3>
The above automaton definition uses a single initial state, which is not necessary. Sometimes, NFAs are defined with a set of initial states. There is an easy construction that translates an NFA with multiple initial states to an NFA with a single initial state, which provides a convenient notation.

<h2 id="example">Example</h2>
<table><tbody><tr><td></td><td></td></tr><tr><td colspan="2"></td></tr></tbody></table>
The following automaton M, with a binary alphabet, determines if the input ends with a 1.
Let 
 
 
 
 M
 =
 (
 {
 p
 ,
 q
 }
 ,
 {
 0
 ,
 1
 }
 ,
 δ
 ,
 p
 ,
 {
 q
 }
 )
 
 
 {\displaystyle M=(\{p,q\},\{0,1\},\delta ,p,\{q\})}
 
 where
the transition function 
 
 
 
 δ
 
 
 {\displaystyle \delta }
 
 can be defined by this <a href="/facts/State_transition_table/eK0E4j8R">state transition table</a> (cf. upper left picture):

State

Input
                        
                      
                    
                  
                
                
                  0
                
                
                  1
                
              
              
                
                  p
                
                
                  {
                  p
                  }
                
                
                  {
                  p
                  ,
                  q
                  }
                
              
              
                
                  q
                
                
                  ∅
                
                
                  ∅
                
              
            
          
        
      
    
    {\displaystyle {\begin{array}{|c|cc|}{\bcancel {{}_{\text{State}}\quad {}^{\text{Input}}}}&0&1\\\hline p&\{p\}&\{p,q\}\\q&\emptyset &\emptyset \end{array}}}

Since the set 
 
 
 
 δ
 (
 p
 ,
 1
 )
 
 
 {\displaystyle \delta (p,1)}
 
 contains more than one state, M is nondeterministic.
The language of M can be described by the <a href="/facts/Regular_language/ahxw67T1">regular language</a> given by the <a href="/facts/Regular_expression/KFL3veHX">regular expression</a> (0|1)*1.
All possible state sequences for the input string "1011" are shown in the lower picture.
The string is accepted by M since one state sequence satisfies the above definition; it does not matter that other sequences fail to do so.
The picture can be interpreted in a couple of ways:

<ul><li>In terms of the above "lucky-run" explanation, each path in the picture denotes a sequence of choices of M.</li>
<li>In terms of the "cloning" explanation, each vertical column shows all clones of M at a given point in time, multiple arrows emanating from a node indicate cloning, a node without emanating arrows indicating the "death" of a clone.</li></ul>
The feasibility to read the same picture in two ways also indicates the equivalence of both above explanations.

<ul><li>Considering the first of the above formal definitions, "1011" is accepted since when reading it M may traverse the state sequence 
 
 
 
 ⟨
 
 r
 
 0
 
 
 ,
 
 r
 
 1
 
 
 ,
 
 r
 
 2
 
 
 ,
 
 r
 
 3
 
 
 ,
 
 r
 
 4
 
 
 ⟩
 =
 ⟨
 p
 ,
 p
 ,
 p
 ,
 p
 ,
 q
 ⟩
 
 
 {\displaystyle \langle r_{0},r_{1},r_{2},r_{3},r_{4}\rangle =\langle p,p,p,p,q\rangle }
 
, which satisfies conditions 1 to 3.</li>
<li>Concerning the second formal definition, bottom-up computation shows that 
 
 
 
 
 δ
 
 ∗
 
 
 (
 p
 ,
 ϵ
 )
 =
 {
 p
 }
 
 
 {\displaystyle \delta ^{*}(p,\epsilon )=\{p\}}
 
, hence 
 
 
 
 
 δ
 
 ∗
 
 
 (
 p
 ,
 1
 )
 =
 δ
 (
 p
 ,
 1
 )
 =
 {
 p
 ,
 q
 }
 
 
 {\displaystyle \delta ^{*}(p,1)=\delta (p,1)=\{p,q\}}
 
, hence 
 
 
 
 
 δ
 
 ∗
 
 
 (
 p
 ,
 10
 )
 =
 δ
 (
 p
 ,
 0
 )
 ∪
 δ
 (
 q
 ,
 0
 )
 =
 {
 p
 }
 ∪
 {
 }
 
 
 {\displaystyle \delta ^{*}(p,10)=\delta (p,0)\cup \delta (q,0)=\{p\}\cup \{\}}
 
, hence 
 
 
 
 
 δ
 
 ∗
 
 
 (
 p
 ,
 101
 )
 =
 δ
 (
 p
 ,
 1
 )
 =
 {
 p
 ,
 q
 }
 
 
 {\displaystyle \delta ^{*}(p,101)=\delta (p,1)=\{p,q\}}
 
, and hence 
 
 
 
 
 δ
 
 ∗
 
 
 (
 p
 ,
 1011
 )
 =
 δ
 (
 p
 ,
 1
 )
 ∪
 δ
 (
 q
 ,
 1
 )
 =
 {
 p
 ,
 q
 }
 ∪
 {
 }
 
 
 {\displaystyle \delta ^{*}(p,1011)=\delta (p,1)\cup \delta (q,1)=\{p,q\}\cup \{\}}
 
; since that set is not disjoint from 
 
 
 
 {
 q
 }
 
 
 {\displaystyle \{q\}}
 
, the string "1011" is accepted.</li></ul>
In contrast, the string "10" is rejected by M (all possible state sequences for that input are shown in the upper right picture), since there is no way to reach the only accepting state, q, by reading the final 0 symbol. While q can be reached after consuming the initial "1", this does not mean that the input "10" is accepted; rather, it means that an input string "1" would be accepted.

<h2 id="equivalence-to-dfa">Equivalence to DFA</h2>
A <a href="/facts/Deterministic_finite_automaton/9conRLFS">deterministic finite automaton</a> (DFA) can be seen as a special kind of NFA, in which for each state and symbol, the transition function has exactly one state. Thus, it is clear that every <a href="/facts/Formal_language/crDTyP8q">formal language</a> that can be recognized by a DFA can be recognized by an NFA.
Conversely, for each NFA, there is a DFA such that it recognizes the same formal language. The DFA can be constructed using the <a href="/facts/Powerset_construction/FeTghmH7">powerset construction</a>.
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 2n states, which sometimes makes the construction impractical for large NFAs.

<h2 id="nfa-with--moves">NFA with ε-moves</h2>
Nondeterministic finite automaton with ε-moves (NFA-ε) is a further generalization to NFA. In this kind of automaton, the transition function is additionally defined on the <a href="/facts/Empty_string/T7udJlmQ">empty string</a> ε. A transition without consuming an input symbol is called an ε-transition and is represented in state diagrams by an arrow labeled "ε". ε-transitions provide a convenient way of modeling systems whose current states are not precisely known: i.e., if we are modeling a system and it is not clear whether the current state (after processing some input string) should be q or q', then we can add an ε-transition between these two states, thus putting the automaton in both states simultaneously.

<h3>Formal definition</h3>
An NFA-ε is represented formally by a 5-<a href="/facts/Tuple/BI1HIxL8">tuple</a>, 
 
 
 
 (
 Q
 ,
 Σ
 ,
 δ
 ,
 
 q
 
 0
 
 
 ,
 F
 )
 
 
 {\displaystyle (Q,\Sigma ,\delta ,q_{0},F)}
 
, consisting of

<ul><li>a finite <a href="/facts/Set_(mathematics)/BfucfHMq">set</a> of <a href="/facts/State_(computer_science)/4Yu8xXHS">states</a> 
 
 
 
 Q
 
 
 {\displaystyle Q}
 
</li>
<li>a finite set of <a href="/facts/Input_symbol/6KW9qYRW">input symbols</a> called the <a href="/facts/Alphabet_(computer_science)/6KW9qYRW">alphabet</a> 
 
 
 
 Σ
 
 
 {\displaystyle \Sigma }
 
</li>
<li>a transition <a href="/facts/Function_(mathematics)/CdReEKCh">function</a> 
 
 
 
 δ
 :
 Q
 ×
 (
 Σ
 ∪
 {
 ϵ
 }
 )
 →
 
 
 P
 
 
 (
 Q
 )
 
 
 {\displaystyle \delta :Q\times (\Sigma \cup \{\epsilon \})\rightarrow {\mathcal {P}}(Q)}
 
</li>
<li>an initial (or <a href="/facts/Finite-state_machine/GMusWd0a">start</a>) state 
 
 
 
 
 q
 
 0
 
 
 ∈
 Q
 
 
 {\displaystyle q_{0}\in Q}
 
</li>
<li>a set of states 
 
 
 
 F
 
 
 {\displaystyle F}
 
 distinguished as <a href="/facts/Finite-state_machine/GMusWd0a">accepting (or final) states</a> 
 
 
 
 F
 ⊆
 Q
 
 
 {\displaystyle F\subseteq Q}
 
.</li></ul>
Here, 
 
 
 
 
 
 P
 
 
 (
 Q
 )
 
 
 {\displaystyle {\mathcal {P}}(Q)}
 
 denotes the <a href="/facts/Power_set/FVuf8PDD">power set</a> of 
 
 
 
 Q
 
 
 {\displaystyle Q}
 
 and 
 
 
 
 ϵ
 
 
 {\displaystyle \epsilon }
 
 denotes empty string.

<h3>ε-closure of a state or set of states</h3>
For a state 
 
 
 
 q
 ∈
 Q
 
 
 {\displaystyle q\in Q}
 
, let 
 
 
 
 E
 (
 q
 )
 
 
 {\displaystyle E(q)}
 
 denote the set of states that are reachable from 
 
 
 
 q
 
 
 {\displaystyle q}
 
 by following ε-transitions in the transition function 
 
 
 
 δ
 
 
 {\displaystyle \delta }
 
, i.e.,

p
 ∈
 E
 (
 q
 )
 
 
 {\displaystyle p\in E(q)}
 
 if there is a sequence of states 
 
 
 
 
 q
 
 1
 
 
 ,
 .
 .
 .
 ,
 
 q
 
 k
 
 
 
 
 {\displaystyle q_{1},...,q_{k}}
 
 such that

<ul><li>
 
 
 
 
 q
 
 1
 
 
 =
 q
 
 
 {\displaystyle q_{1}=q}
 
,</li>
<li>
 
 
 
 
 q
 
 i
 +
 1
 
 
 ∈
 δ
 (
 
 q
 
 i
 
 
 ,
 ε
 )
 
 
 {\displaystyle q_{i+1}\in \delta (q_{i},\varepsilon )}
 
 for each 
 
 
 
 1
 ≤
 i
 <
 k
 
 
 {\displaystyle 1\leq i<k}
 
, and</li>
<li>
 
 
 
 
 q
 
 k
 
 
 =
 p
 
 
 {\displaystyle q_{k}=p}
 
.</li></ul>

 
 
 
 E
 (
 q
 )
 
 
 {\displaystyle E(q)}
 
 is known as the epsilon closure, (also ε-closure) of 
 
 
 
 q
 
 
 {\displaystyle q}
 
.
The ε-closure of a set 
 
 
 
 P
 
 
 {\displaystyle P}
 
 of states of an NFA is defined as the set of states reachable from any state in 
 
 
 
 P
 
 
 {\displaystyle P}
 
 following ε-transitions. Formally, for 
 
 
 
 P
 ⊆
 Q
 
 
 {\displaystyle P\subseteq Q}
 
, define 
 
 
 
 E
 (
 P
 )
 =
 
 ⋃
 
 q
 ∈
 P
 
 
 E
 (
 q
 )
 
 
 {\displaystyle E(P)=\bigcup \limits _{q\in P}E(q)}
 
.

<h3>Extended transition function</h3>
Similar to NFA without ε-moves, the transition function 
 
 
 
 δ
 
 
 {\displaystyle \delta }
 
 of an NFA-ε can be extended to strings.
Informally, 
 
 
 
 
 δ
 
 ∗
 
 
 (
 q
 ,
 w
 )
 
 
 {\displaystyle \delta ^{*}(q,w)}
 
 denotes the set of all states the automaton may have reached when starting in state 
 
 
 
 q
 ∈
 Q
 
 
 {\displaystyle q\in Q}
 
 and reading the string 
 
 
 
 w
 ∈
 
 Σ
 
 ∗
 
 
 .
 
 
 {\displaystyle w\in \Sigma ^{*}.}

The function 
 
 
 
 
 δ
 
 ∗
 
 
 :
 Q
 ×
 
 Σ
 
 ∗
 
 
 →
 
 
 P
 
 
 (
 Q
 )
 
 
 {\displaystyle \delta ^{*}:Q\times \Sigma ^{*}\rightarrow {\mathcal {P}}(Q)}
 
 can be defined recursively as follows.

<ul><li>
 
 
 
 
 δ
 
 ∗
 
 
 (
 q
 ,
 ε
 )
 =
 E
 (
 q
 )
 
 
 {\displaystyle \delta ^{*}(q,\varepsilon )=E(q)}
 
, for each state 
 
 
 
 q
 ∈
 Q
 ,
 
 
 {\displaystyle q\in Q,}
 
 and where 
 
 
 
 E
 
 
 {\displaystyle E}
 
 denotes the epsilon closure;</li></ul>
Informally: Reading the empty string may drive the automaton from state 
 
 
 
 q
 
 
 {\displaystyle q}
 
 to any state of the epsilon closure of 
 
 
 
 q
 .
 
 
 {\displaystyle q.}

<ul><li>
 
 
 
 
 δ
 
 ∗
 
 
 (
 q
 ,
 w
 a
 )
 =
 
 ⋃
 
 r
 ∈
 
 δ
 
 ∗
 
 
 (
 q
 ,
 w
 )
 
 
 E
 (
 δ
 (
 r
 ,
 a
 )
 )
 ,
 
 
 {\textstyle \delta ^{*}(q,wa)=\bigcup _{r\in \delta ^{*}(q,w)}E(\delta (r,a)),}
 
 for each state 
 
 
 
 q
 ∈
 Q
 ,
 
 
 {\displaystyle q\in Q,}
 
 each string 
 
 
 
 w
 ∈
 
 Σ
 
 ∗
 
 
 
 
 {\displaystyle w\in \Sigma ^{*}}
 
 and each symbol 
 
 
 
 a
 ∈
 Σ
 .
 
 
 {\displaystyle a\in \Sigma .}
 
</li></ul>
Informally: Reading the string 
 
 
 
 w
 
 
 {\displaystyle w}
 
 may drive the automaton from state 
 
 
 
 q
 
 
 {\displaystyle q}
 
 to any state 
 
 
 
 r
 
 
 {\displaystyle r}
 
 in the recursively computed set 
 
 
 
 
 δ
 
 ∗
 
 
 (
 q
 ,
 w
 )
 
 
 {\displaystyle \delta ^{*}(q,w)}
 
; after that, reading the symbol 
 
 
 
 a
 
 
 {\displaystyle a}
 
 may drive it from 
 
 
 
 r
 
 
 {\displaystyle r}
 
 to any state in the epsilon closure of 
 
 
 
 δ
 (
 r
 ,
 a
 )
 .
 
 
 {\displaystyle \delta (r,a).}

The automaton is said to accept a string 
 
 
 
 w
 
 
 {\displaystyle w}
 
 if

δ
          
            ∗
          
        
        (
        
          q
          
            0
          
        
        ,
        w
        )
        ∩
        F
        ≠
        ∅
        ,
      
    
    {\displaystyle \delta ^{*}(q_{0},w)\cap F\neq \emptyset ,}

that is, if reading 
 
 
 
 w
 
 
 {\displaystyle w}
 
 may drive the automaton from its start state 
 
 
 
 
 q
 
 0
 
 
 
 
 {\displaystyle q_{0}}
 
 to some accepting state in 
 
 
 
 F
 .
 
 
 {\displaystyle F.}
 
<a class="footnote-ref" id="fnref:14" href="#fn:14">14</a>

<h3>Example</h3>

Let 
 
 
 
 M
 
 
 {\displaystyle M}
 
 be a NFA-ε, with a binary alphabet, that determines if the input contains an even number of 0s or an even number of 1s. Note that 0 occurrences is an even number of occurrences as well.
In formal notation, let 
 
 
 
 M
 =
 (
 {
 
 S
 
 0
 
 
 ,
 
 S
 
 1
 
 
 ,
 
 S
 
 2
 
 
 ,
 
 S
 
 3
 
 
 ,
 
 S
 
 4
 
 
 }
 ,
 {
 0
 ,
 1
 }
 ,
 δ
 ,
 
 S
 
 0
 
 
 ,
 {
 
 S
 
 1
 
 
 ,
 
 S
 
 3
 
 
 }
 )
 
 
 {\displaystyle M=(\{S_{0},S_{1},S_{2},S_{3},S_{4}\},\{0,1\},\delta ,S_{0},\{S_{1},S_{3}\})}
 
 where
the transition relation 
 
 
 
 δ
 
 
 {\displaystyle \delta }
 
 can be defined by this <a href="/facts/State_transition_table/eK0E4j8R">state transition table</a>:

<table><tbody><tr><th>InputState</th><th>0</th><th>1</th><th>ε</th></tr><tr><th>S0</th><td>{}</td><td>{}</td><td>{S1, S3}</td></tr><tr><th>S1</th><td>{S2}</td><td>{S1}</td><td>{}</td></tr><tr><th>S2</th><td>{S1}</td><td>{S2}</td><td>{}</td></tr><tr><th>S3</th><td>{S3}</td><td>{S4}</td><td>{}</td></tr><tr><th>S4</th><td>{S4}</td><td>{S3}</td><td>{}</td></tr></tbody></table>

 
 
 
 M
 
 
 {\displaystyle M}
 
 can be viewed as the union of two <a href="/facts/Deterministic_finite_automaton/9conRLFS">DFAs</a>: one with states 
 
 
 
 {
 
 S
 
 1
 
 
 ,
 
 S
 
 2
 
 
 }
 
 
 {\displaystyle \{S_{1},S_{2}\}}
 
 and the other with states 
 
 
 
 {
 
 S
 
 3
 
 
 ,
 
 S
 
 4
 
 
 }
 
 
 {\displaystyle \{S_{3},S_{4}\}}
 
. 
The language of 
 
 
 
 M
 
 
 {\displaystyle M}
 
 can be described by the <a href="/facts/Regular_language/ahxw67T1">regular language</a> given by this <a href="/facts/Regular_expression/KFL3veHX">regular expression</a> 
 
 
 
 (
 
 1
 
 ∗
 
 
 
 01
 
 ∗
 
 
 
 01
 
 ∗
 
 
 
 )
 
 ∗
 
 
 ∪
 (
 
 0
 
 ∗
 
 
 
 10
 
 ∗
 
 
 
 10
 
 ∗
 
 
 
 )
 
 ∗
 
 
 
 
 {\displaystyle (1^{*}01^{*}01^{*})^{*}\cup (0^{*}10^{*}10^{*})^{*}}
 
.
We define 
 
 
 
 M
 
 
 {\displaystyle M}
 
 using ε-moves but 
 
 
 
 M
 
 
 {\displaystyle M}
 
 can be defined without using ε-moves.

<h3>Equivalence to NFA</h3>
To show NFA-ε is equivalent to NFA, first note that NFA is a special case of NFA-ε, so it remains to show for every NFA-ε, there exists an equivalent NFA.
Given an NFA with epsilon moves 
 
 
 
 M
 =
 (
 Q
 ,
 Σ
 ,
 δ
 ,
 
 q
 
 0
 
 
 ,
 F
 )
 ,
 
 
 {\displaystyle M=(Q,\Sigma ,\delta ,q_{0},F),}

define an NFA 
 
 
 
 
 M
 ′
 
 =
 (
 Q
 ,
 Σ
 ,
 
 δ
 ′
 
 ,
 
 q
 
 0
 
 
 ,
 
 F
 ′
 
 )
 ,
 
 
 {\displaystyle M'=(Q,\Sigma ,\delta ',q_{0},F'),}
 
 where

F
          ′
        
        =
        
          
            {
            
              
                
                  F
                  ∪
                  {
                  
                    q
                    
                      0
                    
                  
                  }
                
                
                  
                     if 
                  
                  E
                  (
                  
                    q
                    
                      0
                    
                  
                  )
                  ∩
                  F
                  ≠
                  {
                  }
                
              
              
                
                  F
                
                
                  
                     otherwise 
                  
                
              
            
            
          
        
      
    
    {\displaystyle F'={\begin{cases}F\cup \{q_{0}\}&{\text{ if }}E(q_{0})\cap F\neq \{\}\\F&{\text{ otherwise }}\\\end{cases}}}

and

δ
 ′
 
 (
 q
 ,
 a
 )
 =
 
 δ
 
 ∗
 
 
 (
 q
 ,
 a
 )
 
 
 {\displaystyle \delta '(q,a)=\delta ^{*}(q,a)}
 
 for each state 
 
 
 
 q
 ∈
 Q
 
 
 {\displaystyle q\in Q}
 
 and each symbol 
 
 
 
 a
 ∈
 Σ
 ,
 
 
 {\displaystyle a\in \Sigma ,}
 
 using the extended transition function 
 
 
 
 
 δ
 
 ∗
 
 
 
 
 {\displaystyle \delta ^{*}}
 
 defined above.
One has to distinguish the transition functions of 
 
 
 
 M
 
 
 {\displaystyle M}
 
 and 
 
 
 
 
 M
 ′
 
 ,
 
 
 {\displaystyle M',}
 
 viz. 
 
 
 
 δ
 
 
 {\displaystyle \delta }
 
 and 
 
 
 
 
 δ
 ′
 
 ,
 
 
 {\displaystyle \delta ',}
 
 and their extensions to strings, 
 
 
 
 δ
 
 
 {\displaystyle \delta }
 
 and 
 
 
 
 
 δ
 
 ′
 
 ∗
 
 
 
 ,
 
 
 {\displaystyle \delta '^{*},}
 
 respectively.
By construction, 
 
 
 
 
 M
 ′
 
 
 
 {\displaystyle M'}
 
 has no ε-transitions.
One can prove that 
 
 
 
 
 δ
 
 ′
 
 ∗
 
 
 
 (
 
 q
 
 0
 
 
 ,
 w
 )
 =
 
 δ
 
 ∗
 
 
 (
 
 q
 
 0
 
 
 ,
 w
 )
 
 
 {\displaystyle \delta '^{*}(q_{0},w)=\delta ^{*}(q_{0},w)}
 
 for each string 
 
 
 
 w
 ≠
 ε
 
 
 {\displaystyle w\neq \varepsilon }
 
, by <a href="/facts/Mathematical_induction/KxAPqNrH">induction</a> on the length of 
 
 
 
 w
 .
 
 
 {\displaystyle w.}

Based on this, one can show that 
 
 
 
 
 δ
 
 ′
 
 ∗
 
 
 
 (
 
 q
 
 0
 
 
 ,
 w
 )
 ∩
 
 F
 ′
 
 ≠
 {
 }
 
 
 {\displaystyle \delta '^{*}(q_{0},w)\cap F'\neq \{\}}
 
 if, and only if, 
 
 
 
 
 δ
 
 ∗
 
 
 (
 
 q
 
 0
 
 
 ,
 w
 )
 ∩
 F
 ≠
 {
 }
 ,
 
 
 {\displaystyle \delta ^{*}(q_{0},w)\cap F\neq \{\},}
 
 for each string 
 
 
 
 w
 ∈
 
 Σ
 
 ∗
 
 
 :
 
 
 {\displaystyle w\in \Sigma ^{*}:}

<ul><li>If 
 
 
 
 w
 =
 ε
 ,
 
 
 {\displaystyle w=\varepsilon ,}
 
 this follows from the definition of 
 
 
 
 
 F
 ′
 
 .
 
 
 {\displaystyle F'.}
 
</li>
<li>Otherwise, let 
 
 
 
 w
 =
 v
 a
 
 
 {\displaystyle w=va}
 
 with 
 
 
 
 v
 ∈
 
 Σ
 
 ∗
 
 
 
 
 {\displaystyle v\in \Sigma ^{*}}
 
 and 
 
 
 
 a
 ∈
 Σ
 .
 
 
 {\displaystyle a\in \Sigma .}
 
</li></ul>
From 
 
 
 
 
 δ
 
 ′
 
 ∗
 
 
 
 (
 
 q
 
 0
 
 
 ,
 w
 )
 =
 
 δ
 
 ∗
 
 
 (
 
 q
 
 0
 
 
 ,
 w
 )
 
 
 {\displaystyle \delta '^{*}(q_{0},w)=\delta ^{*}(q_{0},w)}
 
 and 
 
 
 
 F
 ⊆
 
 F
 ′
 
 ,
 
 
 {\displaystyle F\subseteq F',}
 
 we have 
 
 
 
 
 δ
 
 ′
 
 ∗
 
 
 
 (
 
 q
 
 0
 
 
 ,
 w
 )
 ∩
 
 F
 ′
 
 ≠
 {
 }
 
 ⇐
 
 
 δ
 
 ∗
 
 
 (
 
 q
 
 0
 
 
 ,
 w
 )
 ∩
 F
 ≠
 {
 }
 ;
 
 
 {\displaystyle \delta '^{*}(q_{0},w)\cap F'\neq \{\}\;\Leftarrow \;\delta ^{*}(q_{0},w)\cap F\neq \{\};}
 
 we still have to show the "
 
 
 
 ⇒
 
 
 {\displaystyle \Rightarrow }
 
" direction.
<ul><li>If 
 
 
 
 
 δ
 
 ′
 
 ∗
 
 
 
 (
 
 q
 
 0
 
 
 ,
 w
 )
 
 
 {\displaystyle \delta '^{*}(q_{0},w)}
 
 contains a state in 
 
 
 
 
 F
 ′
 
 ∖
 {
 
 q
 
 0
 
 
 }
 ,
 
 
 {\displaystyle F'\setminus \{q_{0}\},}
 
 then 
 
 
 
 
 δ
 
 ∗
 
 
 (
 
 q
 
 0
 
 
 ,
 w
 )
 
 
 {\displaystyle \delta ^{*}(q_{0},w)}
 
 contains the same state, which lies in 
 
 
 
 F
 
 
 {\displaystyle F}
 
.</li>
<li>If 
 
 
 
 
 δ
 
 ′
 
 ∗
 
 
 
 (
 
 q
 
 0
 
 
 ,
 w
 )
 
 
 {\displaystyle \delta '^{*}(q_{0},w)}
 
 contains 
 
 
 
 
 q
 
 0
 
 
 ,
 
 
 {\displaystyle q_{0},}
 
 and 
 
 
 
 
 q
 
 0
 
 
 ∈
 F
 ,
 
 
 {\displaystyle q_{0}\in F,}
 
 then 
 
 
 
 
 δ
 
 ∗
 
 
 (
 
 q
 
 0
 
 
 ,
 w
 )
 
 
 {\displaystyle \delta ^{*}(q_{0},w)}
 
 also contains a state in 
 
 
 
 F
 ,
 
 
 {\displaystyle F,}
 
 viz. 
 
 
 
 
 q
 
 0
 
 
 .
 
 
 {\displaystyle q_{0}.}
 
</li>
<li>If 
 
 
 
 
 δ
 
 ′
 
 ∗
 
 
 
 (
 
 q
 
 0
 
 
 ,
 w
 )
 
 
 {\displaystyle \delta '^{*}(q_{0},w)}
 
 contains 
 
 
 
 
 q
 
 0
 
 
 ,
 
 
 {\displaystyle q_{0},}
 
 and 
 
 
 
 
 q
 
 0
 
 
 ∉
 F
 ,
 
 
 {\displaystyle q_{0}\not \in F,}
 
 but 
 
 
 
 
 q
 
 0
 
 
 ∈
 
 F
 ′
 
 ,
 
 
 {\displaystyle q_{0}\in F',}
 
 then there exists a state in 
 
 
 
 E
 (
 
 q
 
 0
 
 
 )
 ∩
 F
 
 
 {\displaystyle E(q_{0})\cap F}
 
, and the same state must be in 
 
 
 
 
 δ
 
 ∗
 
 
 (
 
 q
 
 0
 
 
 ,
 w
 )
 =
 
 ⋃
 
 r
 ∈
 
 δ
 
 ∗
 
 
 (
 q
 ,
 v
 )
 
 
 E
 (
 δ
 (
 r
 ,
 a
 )
 )
 .
 
 
 {\textstyle \delta ^{*}(q_{0},w)=\bigcup _{r\in \delta ^{*}(q,v)}E(\delta (r,a)).}
 
<a class="footnote-ref" id="fnref:15" href="#fn:15">15</a></li></ul>
Since NFA is equivalent to DFA, NFA-ε is also equivalent to DFA.

<h2 id="closure-properties">Closure properties</h2>

The set of languages recognized by NFAs is <a href="/facts/Closed_under/Ct6r2fJz">closed under</a> the following operations. These closure operations are used in <a href="/facts/Thompson%27s_construction_algorithm/ey41ImSF">Thompson's construction algorithm</a>, which constructs an NFA from any <a href="/facts/Regular_expression/KFL3veHX">regular expression</a>. They can also be used to prove that NFAs recognize exactly the <a href="/facts/Regular_languages/ahxw67T1">regular languages</a>.

<ul><li>Union (cf. picture); that is, if the language L1 is accepted by some NFA A1 and L2 by some A2, then an NFA Au can be constructed that accepts the language L1∪L2.</li>
<li>Intersection; similarly, from A1 and A2 an NFA Ai can be constructed that accepts L1∩L2.</li>
<li>Concatenation</li>
<li>Negation; similarly, from A1 an NFA An can be constructed that accepts Σ*\L1.</li>
<li><a href="/facts/Kleene_closure/I6SX0f2Y">Kleene closure</a></li></ul>
Since NFAs are equivalent to nondeterministic finite automaton with ε-moves (NFA-ε), the above closures are proved using closure properties of NFA-ε.

<h2 id="properties">Properties</h2>
The machine starts in the specified initial state and reads in a string of symbols from its <a href="/facts/Alphabet_(computer_science)/6KW9qYRW">alphabet</a>. The automaton uses the <a href="/facts/State_transition_function/GMusWd0a">state transition function</a> Δ to determine the next state using the current state, and the symbol just read or the empty string. However, "the next state of an NFA depends not only on the current input event, but also on an arbitrary number of subsequent input events. Until these subsequent events occur it is not possible to determine which state the machine is in".<a class="footnote-ref" id="fnref:16" href="#fn:16">16</a> If, when the automaton has finished reading, it is in an accepting state, the NFA is said to accept the string, otherwise it is said to reject the string.
The set of all strings accepted by an NFA is the language the NFA accepts. This language is a <a href="/facts/Regular_language/ahxw67T1">regular language</a>.
For every NFA a <a href="/facts/Deterministic_finite_automaton/9conRLFS">deterministic finite automaton</a> (DFA) can be found that accepts the same language. Therefore, it is possible to convert an existing NFA into a DFA for the purpose of implementing a (perhaps) simpler machine. This can be performed using the <a href="/facts/Powerset_construction/FeTghmH7">powerset construction</a>, which may lead to an exponential rise in the number of necessary states. For a formal proof of the powerset construction, please see the <a href="/facts/Powerset_construction/FeTghmH7">Powerset construction</a> article.

<h2 id="implementation">Implementation</h2>
There are many ways to implement a NFA:

<ul><li>Convert to the equivalent DFA. In some cases this may cause exponential blowup in the number of states.<a class="footnote-ref" id="fnref:17" href="#fn:17">17</a></li>
<li>Keep a <a href="/facts/Set_data_structure/ovoXUmF9">set data structure</a> of all states which the NFA might currently be in. On the consumption of an input symbol, <a href="/facts/Set_union/KVVXKfWl">unite</a> 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 s2 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 <a href="/facts/Big_O_notation/weFFjSWg">O</a>(ns2),<a class="footnote-ref" id="fnref:18" href="#fn:18">18</a> and space O(s).</li>
<li>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.)</li>
<li>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.)<a class="footnote-ref" id="fnref:19" href="#fn:19">19</a></li></ul>
<h2 id="complexity">Complexity</h2>
<ul><li>One can solve in linear time the <a href="/facts/Emptiness_problem/ho61ybCq">emptiness problem</a> for NFA, i.e., check whether the language of a given NFA is empty. To do this, we can simply perform a <a href="/facts/Depth-first_search/luxJKVph">depth-first search</a> from the initial state and check if some final state can be reached.</li>
<li>It is <a href="/facts/PSPACE/RIkAClvG">PSPACE</a>-complete to test, given an NFA, whether it is universal, i.e., if there is a string that it does not accept.<a class="footnote-ref" id="fnref:20" href="#fn:20">20</a> 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.</li>
<li>Given as input an NFA A and an integer n, the <a href="/facts/Counting_problem_(complexity)/pFj5xFYt">counting problem</a> of determining how many words of length n are accepted by A is intractable; it is <a href="/facts/%E2%99%AFP/tY95TU7t">#P-hard</a>. In fact, this problem is complete (under <a href="/facts/Parsimonious_reduction/q41sFqcY">parsimonious reductions</a>) for the complexity class SpanL.<a class="footnote-ref" id="fnref:21" href="#fn:21">21</a></li></ul>
<h2 id="application-of-nfa">Application of NFA</h2>
NFAs and DFAs are equivalent in that if a language is recognized by an NFA, it is also recognized by a DFA and vice versa. The establishment of such equivalence is important and useful. It is useful because constructing an NFA to recognize a given language is sometimes much easier than constructing a DFA for that language. It is important because NFAs can be used to reduce the complexity of the mathematical work required to establish many important properties in the <a href="/facts/Theory_of_computation/xYJd2YeI">theory of computation</a>. For example, it is much easier to prove <a href="/facts/Regular_languages/ahxw67T1">closure properties</a> of <a href="/facts/Regular_language/ahxw67T1">regular languages</a> using NFAs than DFAs.

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Deterministic_finite_automaton/9conRLFS">Deterministic finite automaton</a></li>
<li><a href="/facts/Two-way_nondeterministic_finite_automaton/0JQRrb4E">Two-way nondeterministic finite automaton</a></li>
<li><a href="/facts/Pushdown_automaton/kEPRC70F">Pushdown automaton</a></li>
<li><a href="/facts/Nondeterministic_Turing_machine/zv2x6XPG">Nondeterministic Turing machine</a></li></ul>
<h2 id="notes">Notes</h2>

<ul><li>Rabin, M. O.; Scott, D. (April 1959). "Finite Automata and Their Decision Problems". IBM Journal of Research and Development. 3 (2): 114–125. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1147%2Frd.32.0114">10.1147/rd.32.0114</a>.</li>
<li><a href="/facts/Michael_Sipser/h5Wg22bh">Sipser, Michael</a> (1997). <a href="/facts/Introduction_to_the_Theory_of_Computation/CXXk8vfj">Introduction to the Theory of Computation</a> (1st ed.). PWS Publishing. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-534-94728-6. (<a href="https://archive.org/details/introductiontoth00sips">accessible to patrons with print disabilities</a>) (See §1.2: Nondeterminism, pp. 47–63.)</li>
<li>Hopcroft, John E.; Ullman, Jeffrey D. (1979). Introduction to Automata Theory, Languages, and Computation (1st ed.). Addison-Wesley. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-201-02988-X. (<a href="https://archive.org/details/introductiontoau00hopc">accessible to patrons with print disabilities</a>)</li>
<li><a href="/facts/John_Hopcroft/j42ejf1m">Hopcroft, John E.</a>; <a href="/facts/Rajeev_Motwani/v0K0IYQm">Motwani, Rajeev</a>; <a href="/facts/Jeffrey_Ullman/7AqlHj4f">Ullman, Jeffrey D.</a> (2006) [1979]. <a href="/facts/Introduction_to_Automata_Theory,_Languages,_and_Computation/PsuI05rR">Introduction to Automata Theory, Languages, and Computation</a> (3rd ed.). Addison-Wesley. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-321-45536-3. (See chapter 2, "Finite Automata".)</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Martin, John (2010). Introduction to Languages and the Theory of Computation. McGraw Hill. p. 108. ISBN 978-0071289429. <a href="978-0071289429" target="_blank">978-0071289429</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Rabin & Scott 1959. - Rabin, M. O.; Scott, D. (April 1959). "Finite Automata and Their Decision Problems". IBM Journal of Research and Development. 3 (2): 114–125. doi:10.1147/rd.32.0114. <a href="https://doi.org/10.1147%2Frd.32.0114" target="_blank">https://doi.org/10.1147%2Frd.32.0114</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">A choice sequence may lead into a "dead end" where no transition is applicable for the current input symbol; in this case it is considered unsuccessful. <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Hopcroft & Ullman 1979, pp. 19–20. - Hopcroft, John E.; Ullman, Jeffrey D. (1979). Introduction to Automata Theory, Languages, and Computation (1st ed.). Addison-Wesley. ISBN 0-201-02988-X. <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Alfred V. Aho and John E. Hopcroft and Jeffrey D. Ullman (1974). The Design and Analysis of Computer Algorithms. Reading/MA: Addison-Wesley. ISBN 0-201-00029-6. <a href="0-201-00029-6" target="_blank">0-201-00029-6</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Hopcroft, Motwani & Ullman 2006, pp. 55–6. - Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2006) [1979]. Introduction to Automata Theory, Languages, and Computation (3rd ed.). Addison-Wesley. ISBN 0-321-45536-3. <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Hopcroft & Ullman 1979, pp. 19–20. - Hopcroft, John E.; Ullman, Jeffrey D. (1979). Introduction to Automata Theory, Languages, and Computation (1st ed.). Addison-Wesley. ISBN 0-201-02988-X. <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Sipser 1997, p. 48. - Sipser, Michael (1997). Introduction to the Theory of Computation (1st ed.). PWS Publishing. ISBN 978-0-534-94728-6. <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Hopcroft, Motwani & Ullman 2006, pp. 55–6. - Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2006) [1979]. Introduction to Automata Theory, Languages, and Computation (3rd ed.). Addison-Wesley. ISBN 0-321-45536-3. <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Alfred V. Aho and John E. Hopcroft and Jeffrey D. Ullman (1974). The Design and Analysis of Computer Algorithms. Reading/MA: Addison-Wesley. ISBN 0-201-00029-6. <a href="0-201-00029-6" target="_blank">0-201-00029-6</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Sipser 1997, p. 54. - Sipser, Michael (1997). Introduction to the Theory of Computation (1st ed.). PWS Publishing. ISBN 978-0-534-94728-6. <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Hopcroft & Ullman 1979, p. 21. - Hopcroft, John E.; Ullman, Jeffrey D. (1979). Introduction to Automata Theory, Languages, and Computation (1st ed.). Addison-Wesley. ISBN 0-201-02988-X. <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">Hopcroft, Motwani & Ullman 2006, p. 59. - Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2006) [1979]. Introduction to Automata Theory, Languages, and Computation (3rd ed.). Addison-Wesley. ISBN 0-321-45536-3. <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">Hopcroft & Ullman 1979, p. 25. - Hopcroft, John E.; Ullman, Jeffrey D. (1979). Introduction to Automata Theory, Languages, and Computation (1st ed.). Addison-Wesley. ISBN 0-201-02988-X. <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
<li id="fn:15">Hopcroft & Ullman 1979, pp. 26–27. - Hopcroft, John E.; Ullman, Jeffrey D. (1979). Introduction to Automata Theory, Languages, and Computation (1st ed.). Addison-Wesley. ISBN 0-201-02988-X. <a href="#fnref:15" class="footnote-back-ref">↩</a></li>
<li id="fn:16">FOLDOC Free Online Dictionary of Computing, Finite-State Machine <a href="http://foldoc.org/nfa" target="_blank">http://foldoc.org/nfa</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></li>
<li id="fn:17">Chris Calabro (February 27, 2005). "NFA to DFA blowup" (PDF). cseweb.ucsd.edu. Retrieved 6 March 2023. <a href="https://cseweb.ucsd.edu//~ccalabro/essays/fsa.pdf" target="_blank">https://cseweb.ucsd.edu//~ccalabro/essays/fsa.pdf</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></li>
<li id="fn:18">Hopcroft, Motwani & Ullman 2006, pp. 154–5. - Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2006) [1979]. Introduction to Automata Theory, Languages, and Computation (3rd ed.). Addison-Wesley. ISBN 0-321-45536-3. <a href="#fnref:18" class="footnote-back-ref">↩</a></li>
<li id="fn:19">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. Adding trace matching with free variables to AspectJ Archived 2009-09-18 at the Wayback Machine. 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. <a href="http://abc.comlab.ox.ac.uk/papers#oopsla2005" target="_blank">http://abc.comlab.ox.ac.uk/papers#oopsla2005</a> <a href="#fnref:19" class="footnote-back-ref">↩</a></li>
<li id="fn:20">Historically shown in: Meyer, A. R.; Stockmeyer, L. J. (1972-10-25). "The equivalence problem for regular expressions with squaring requires exponential space". Proceedings of the 13th Annual Symposium on Switching and Automata Theory (SWAT). USA: IEEE Computer Society: 125–129. doi:10.1109/SWAT.1972.29. For a modern presentation, see [1] <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:20" class="footnote-back-ref">↩</a></li>
<li id="fn:21">Álvarez, Carme; Jenner, Birgit (1993-01-04). "A very hard log-space counting class". Theoretical Computer Science. 107 (1): 3–30. doi:10.1016/0304-3975(93)90252-O. ISSN 0304-3975. <a href="https://dx.doi.org/10.1016/0304-3975%2893%2990252-O" target="_blank">https://dx.doi.org/10.1016/0304-3975%2893%2990252-O</a> <a href="#fnref:21" class="footnote-back-ref">↩</a></li>
</ol>

Nondeterministic finite automaton open-in-new

Nondeterministic finite automaton