Java Reference
In-Depth Information
Finite
Automaton
for A
A
λ
Finite
for B
Automaton
Figure 3.21: An NFA for
AB
.
λ
λ
Finite
Automaton
for A
λ
A
Figure 3.22: An NFA for
A
.
the FA for
A
one or more times so that zero or more strings that belong to
A
are matched.
The transformation from an NFA
N
to an equivalent DFA
D
works by what is
sometimes called the
subset construction
. The subset construction algorithm
is shown in Figure 3.23. The algorithm associates each state of
D
with a
set
of states of
N
. The idea is that
D
will be in state
after reading a given
input string if, and only if,
N
could be in
any
of the states
x
,
y
,or
z
, depending
on the transitions it chooses. Thus,
D
keeps track of all of the possible routes
N
might take and runs them simultaneously. Because
N
is a
finite
automaton,
it has only a finite number of states. The number of subsets of
N
's states is also
finite. This makes tracking various sets of states feasible.
The start state of
D
is the set of all states to which
N
can transition without
reading any input characters—that is, the set of states reachable from the start
state of
N
following only
{
x
,
y
,
z
}
λ
transitions. In Figure 3.23, Algorithm C
lose
, called
from R
λ
transitions. Once the start state of
D
is built, we begin to create successor
states.
ecord
S
tate
, computes those states that can be reached after only
