Next: Finite Automata.
Up: Finite Automata
Previous: Nondeterministic Finite Automata
NFA WITH INSTANTANEOUS TRANSITIONS. A nondeterministic finite automaton with
instantaneous transitions
(or
transitions) consists of six 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 a subset of S,
 a function mapping each state of S
to a subset of S
such that
(, S, I, T,) is a NFA.
The functions and are called
the noninstaneous transition function
and
the
transition function
(or the instaneous transition function).
Such an automaton will be called a NFAIT or an
NFA, for short.
Figure 7:
A nondeterministic finite automaton with instantaneous transitions.

INSTANTANEOUS TRANSITIONS.
Observe that
 The goal of the function is to describe transitions
from one state to others without reading any letter.
One can view also these
transitions from one state
to others as transitions obtained after reading the empty word
.
 In the transition graph of a NFAIT
the
transitions are indicated by edges
(from one state to another) labeled by
.
Figure 8:
A NFAIT
accepting
L_{1} L_{2} L_{3} L_{4}.

THE LANGUAGE ACCEPTED BY A NFAIT. For
A S we define the
closure of
A as the set of the states that can be reached from a
state of A by reading the empty word
.
The
closure of A is denoted by
(A)
and is formally defined by Algorithm 2.
Algorithm 2
 1
 toSee := A;
 2

(A) := A;
 3
 while
toSee repeat
 3.1
 s := first(toSee); toSee := rest(toSee);
 3.2
 for
s' (s) repeat
 3.2.1
 if
(s' toSee) and
(s' (A)) then toSee := cons(s', toSee);
 3.3

(A) := cons(
s,(A));
 4
 return(
(A))
For two states s and s', and for a word w
we define the relation
ss'
by induction on the length  w of w:
 if
w = we have
ss'
for every
s' ({s}),
 if w = vx where v is a word and x is a letter, we have
ss'''
if there exist s', s'' such that
ss',
s'' (s', x) and
s''' ({s''}).
a word w over is accepted (or recognized)
by the NFAIT if there exists an initial
state i and a final state f such that
if.
FROM A NFAIT TO A DFA ACCEPTING THE SAME LANGUAGE.
Theorem 2
Let
= (
,
S,
I,
T,
,
)
be a NFAIT and let
L be the language
accepted by
.
Then there exists a DFA
which accepts
L too.
To construct such an
one proceeds as in
Algorithm 1 with the following
two modifications.
 The initial state is
(I)
instead of
.
 The transition
(A, x) is defined by:
(
A,
x) =
({
s'  (
s A) (
s' (
s,
x))}).
The resulting algorithm is called again the subset algorithm.
Figure 9 shows a DFA accepting the same language
as the NFAIT of Figure 7. This DFA is computed
by means of the subset algorithm.
Let us describe the construction of the transition table of this DFA.
 1.
 The initial state is the
(I) = (1) = 134.
The transitions from it are
(134, a) = 2,
(134, b) =
(134, c) = .
This shows that and 2 are states of the output DFA.
The has to be understood as the errorstate.
If we do not need to produce a complete DFA
then we can discard this errorstate.
 2.
 The transition from state 2 are
(2, a) = 2,
(2, b) = 1234
(2, c) = 1234.
This shows that 1234 is a state of the output DFA.
 3.
 The transition from state 1234 are
(1234, a) = 2,
(1234, b) = 1234
(1234, c) = 1234.
 4.
 The final states of this DFA are its states
which contain at least one of the final states
of the input NFA. Hence the final states are
134 and 1234.
Therefore we obtain the following transition table.

a 
b 
c 
134 
2 


2 
2 
1234 
1234 
1234 
2 
1234 
1234 
Figure 9:
From a NFAIT to a DFA accepting the same language and
produced by the subset algorithm.

REMARKS ABOUT THE NFAITTODFA CONSTRUCTION.
 If the input NFAIT (of the subset algorithm) has q
states then the output DFA has
(2^{q}) states.
 However the states of the DFA computed by this
algorithm have the following property:
they can all be reached on some input word.
In other words, none of these computed states is useless.
 In practice, the number of reachable states
(of the output DFA) is much smaller
than the above exponential upper bound.
 However the DFA constructed by the above algorithm
is not necessarily minimal: it is possible
that the number of states can be further reduced.
Figure 10 shows a DFA
recognizing the same language as the DFA
of Figure 4 but using
6 states instead of 9.
Figure 10:
A minimal DFA
accepting
L_{1} L_{2} L_{3} L_{4}.

Next: Finite Automata.
Up: Finite Automata
Previous: Nondeterministic Finite Automata
Marc Moreno Maza
20041202