Java Reference
In-Depth Information
b
λ
a
1
2
5
a
a
a | b
b
3
4
Figure 3.24: An NFA showing how subset construction operates.
To do this, we place each state
S
of
D
on a work list when it is created. For
each state
S
on thework list and each character
c
in the vocabulary, we compute
S
's successor under
c
.
S
is identified with some set of
N
's states
{
n
1
,
n
2
,...}
.We
find all of the possible successor states to
{
n
1
,
n
2
,...}
under
c
and obtain a set
{
m
1
. The resulting
set of NFA states is included as a state
T
in
D
, and a transition from
S
to
T
,
labeled with
c
, is added to
D
. We continue adding states and transitions to
D
until all possible successors to existing states are added. Because each state
corresponds to a finite subset of
N
's states, the process of adding new states to
D
must eventually terminate.
An accepting state of
D
is any set that contains an accepting state of
N
.
This reflects the convention that
N
accepts if there is
any
way it could get to its
accepting state by choosing the “right” transitions.
To see how the subset construction operates, consider the NFA shown in
Figure 3.24. In the NFA, we start with state 1, the start state of
N
, and add state
2, its
,
m
2
,...}
. Finally, we include the
λ
-successors of
{
m
1
,
m
2
,...}
λ
-successor. Hence,
D
's start state is
{
1
,
2
}
.Under
a
,
{
1
,
2
}
's successor is
{
3
,
4
,
5
}
. State 1 has itself as a successor under
b
. When state 1's
λ
-successor,
2, is included,
{
1
,
2
}
's successor is
{
1
,
2
}
.
{
3
,
4
,
5
}
's successors under
a
and
b
are
{
. Accepting states of
D
are those
state sets that contain
N
's accepting state (5). The resulting DFA is shown in
Figure 3.25.
It can be established that the DFA constructed by M
5
}
and
{
4
,
5
}
.
{
4
,
5
}
's successor under
b
is
{
5
}
is
equivalent to the original NFA (see Exercise 20). What is not obvious is the fact
that the DFA that is built can sometimes be
much
larger than the original NFA.
States of the DFA are identified with sets of NFA states. If the NFA has
n
states,
there are 2
n
distinct sets of NFA states and hence the DFAmay have as many as
2
n
states. Exercise 16 discusses an NFA that actually exhibits this exponential
blowup in size when it is made deterministic. Fortunately, the NFAs built
from the kind of regular expressions used to specify programming language
ake
D
eterministic
