Java Reference
In-Depth Information
a
a
Figure 3.17: An NFA with two
a
transitions.
a
λ
a
Figure 3.18: An NFA with a
λ
transition.
Regular expressions are equivalent to FAs. In fact, the main job of a scanner
generator program such as Lex is to transform a regular expression definition
into an equivalent FA. It does this by first transforming the regular expression
into a
nondeterministic finite automaton (NFA)
. An NFA is a generalization
of a DFA that allows transitions labeled with
λ
as well as multiple transitions
from a state that have the same label.
A scanner generator first creates an NFA from a set of regular-expression
specifications. The NFA is then transformed into a DFA. Both of these steps
are discussed in greater detail in this section.
An NFA, upon reading a particular input, need not make a unique (deter-
ministic) choice of which state to visit. For example, as shown in Figure 3.17,
an NFA is allowed to have a state that has two transitions (shown by the ar-
rows) coming out of it, labeled by the same symbol. As shown in Figure 3.18,
an NFA may also have transitions labeled with
.
Transitions are normally labeled with individual characters in
λ
Σ
,andal-
though
is a string (the string with no characters in it), it is definitely
not
a
character. In the last example, when the FA is in the state at the left and the
next input character is
a
, it may choose either to use the transition labeled
a
or
to first follow the
λ
wherever you look for
it) and
then
follow an
a
transition. FAs that contain no
λ
transition (you can always find
λ
transitions and that
always have unique successor states for any symbol are
deterministic
.
λ
