Java Reference
In-Depth Information
a
λ
Figure 3.19: NFAs for
a
and
λ
.
Finite
A
Automaton
for A
λ
λ
λ
Finite
λ
Automaton
B
for B
Figure 3.20: An NFA for
A
|
B
.
The algorithm to make an FA from a regular expression proceeds in two
steps. First, it transforms the regular expression into an NFA. Then it trans-
forms the NFA into a DFA.
Transforming a regular expression into an NFA is easy. A regular expression
is built of the
atomic
regular expressions
a
(where
a
is a character in
Σ
)and
by using the three operations
AB
,
A
|
B
,and
A
. Other operations (such as
A
+
) are just abbreviations for combinations of these. As shown in Figure 3.19,
NFAs for
a
and
λ
are trivial.
Now suppose we have NFAs for
A
and
B
and want one for
A
|
B
.We
construct the NFA shown in Figure 3.20. The states labeled
A
and
B
were the
accepting states of the automata for
A
and
B
; we create a new accepting state
for the combined FA.
As shown in Figure 3.21, the construction of
AB
is straightforward. The
accepting state of the combined FA is the same as the accepting state of
B
.
Finally, the NFA for
A
is shown in Figure 3.22. The start state is an
accepting state, so
λ
λ
is accepted. Alternatively, we can follow a path through
