Next: Nondeterministic Finite Automata with instantaneous
Up: Finite Automata
Previous: Deterministic Finite Automata
NONDETERMINISTIC FINITE AUTOMATA.
A nondeterministic finite automaton (NFA) consists of five things:
 an input alphabet ,
 a finite set S whose elements are called states,
 a set
I S of distinguished states, called initial states,
 a set
F S of distinguished states, called accepting states,
 a function from
S×
to 2^{S}, thus every statesymbol couple
is mapped by to set of states
(that is a subset of S).
Observe that
 In the transition graph of a NFA the same symbol
a can label two or more transitions
out of one state.
 Therefore after reading a given symbol, a NFA
can have several states.
LANGUAGE RECOGNIZED BY A NFA. A word w is accepted by a NFA if after reading w
the NFA is in at least one accepting state.
Figure 5 shows a NFA and a DFA
recognizing the same language: the language over
= {a, b} consisting of the words
which end with b.
Figure 5:
A NFA and a DFA accepting the same language.

FROM A NFA TO A DFA ACCEPTING THE SAME LANGUAGE.
Theorem 1
Let
= (
,
S,
I,
F,
) be a NFA
accepting the language
L.
Then there exists a DFA
accepting
L too.
To construct such a DFA
from one proceeds as follows.
 The alphabet is unchanged.
 The set
of states of
is a subset of 2^{S}. Hence each state of
is a subset of S.
The set
is computed by
Algorithm 1 below.
 The starting state
of
is the set I of the initial states of
.
 The set
of the accepting states of
is the set of the states
of
such that
F .
 The transition function of
together with
is determined by
Algorithm 1,
called the SUBSET ALGORITHM.
Algorithm 1
 1
 toSee :=
[];
 2

:= [ ];
 3
 while
toSee [ ] repeat
 3.1
 A := first(toSee); toSee := rest(toSee);
 3.2
 for
x repeat
 3.2.1

(A, x) :=
{s'  (s A) (ss')};
 3.2.2
 if (
(A, x) toSee) and (
(A, x) ) then toSee := cons(
(A, x), toSee);
 3.3

:= cons(
A,);
 4
 return(
,)
In this algorithm
 toSee is the list of the states
of
such that the
(a,)
for all
a
have not been computed yet,
 whereas
contains those states
of
for which
(a,)
is known for every
a .
 the functions first, rest and cons
operate on lists and are similar to the
traditional stack routines top, pop and push
respectively.
Figure 6 shows a DFA
obtained from a NFA by applying Algorithm 1.
Figure 6:
Another DFA accepting the same language as the previous NFA.

Remark 1
States are generally denoted with numbers.
So if the states of the input NFA are called
1, 2, 3,...
then the states of the output DFA could be
{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3},
{1, 2, 3}, ....
To simplify notation we denote the subset
{i, j,...},
by ij^{ ... } providing that there is no ambiguity.
Next: Nondeterministic Finite Automata with instantaneous
Up: Finite Automata
Previous: Deterministic Finite Automata
Marc Moreno Maza
20041202