Editing Nondeterministic finite automaton (section)

==Example==
{| style="float: right; border-spacing: 0;"
|-
| VALIGN=TOP | [[File:NFASimpleExample.svg|thumb|250px|The [[state diagram]] for ''M''. It is not deterministic since in state ''p'' reading a 1 can lead to ''p'' or to ''q''.]]
| VALIGN=TOP | [[File:NFASimpleExample Runs10.gif|thumb|250px|All possible runs of ''M'' on input string "10"]]
|-
| COLSPAN=2  | [[File:NFASimpleExample Runs1011.gif|thumb|530px|All possible runs of ''M'' on input string "1011".<br />''Arc label:'' input symbol, ''node label'': state, ''{{color|#00c000|green}}:'' start state, ''{{color|#c00000|red}}:'' accepting state(s).
{| class="wikitable"
|-
! {{diagonal split header|State sequence|Input}}            
!            || 1 ||       || 0 ||       || 1 ||       || 1 ||
|-
| 1 || ''p'' ||   || ''q'' ||   ||'''?'''||   ||       ||   || 
|-
| 2 || ''p'' ||   || ''p'' ||   || ''p'' ||   || ''q'' ||   || '''?'''
|-
| 3 || ''p'' ||   || ''p'' ||   || ''p'' ||   || ''p'' ||   || ''q''
|}
]]
|}
The following automaton {{mvar|M}}, with a binary alphabet, determines if the input ends with a 1.
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):
:<math>\begin{array}{|c|cc|}
\bcancel{{}_\text{State}\quad {}^\text{Input}} &
0 &
1
\\
\hline
p &
\{p\} &
\{p,q\}
\\
q &
\emptyset &
\emptyset
\end{array}</math>
Since the set <math>\delta(p,1)</math> contains more than one state, {{mvar|M}} is nondeterministic.
The language of {{mvar|M}} can be described by the [[regular language]] given by the [[regular expression]] <code>(0|1)*1</code>.

All possible state sequences for the input string "1011" are shown in the lower picture.

The string is accepted by {{mvar|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:
* In terms of the [[#Informal introduction|above]] "lucky-run" explanation, each path in the picture denotes a sequence of choices of {{mvar|M}}.
* In terms of the "cloning" explanation, each vertical column shows all clones of {{mvar|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.
The feasibility to read the same picture in two ways also indicates the equivalence of both above explanations.
* Considering the first of the [[#Recognized language|above]] formal definitions, "1011" is accepted since when reading it {{mvar|M}} may traverse the state sequence <math>\langle r_0,r_1,r_2,r_3,r_4 \rangle = \langle p, p, p, p, q \rangle</math>, which satisfies conditions 1 to 3. 
* Concerning the second formal definition, bottom-up computation shows that <math>\delta^*(p,\epsilon) = \{ p \}</math>, hence <math>\delta^*(p,1) = \delta(p,1) = \{ p,q \}</math>, hence <math>\delta^*(p,10) = \delta(p,0) \cup \delta(q,0) = \{ p \} \cup \{\}</math>, hence <math>\delta^*(p,101) = \delta(p,1) = \{ p,q \}</math>, and hence <math>\delta^*(p,1011) = \delta(p,1) \cup \delta(q,1) = \{ p,q \} \cup \{\}</math>; since that set is not disjoint from <math>\{ q \}</math>, the string "1011" is accepted.

In contrast, the string "10" is rejected by {{mvar|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, {{mvar|q}}, by reading the final 0 symbol. While {{mvar|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.