Java Reference
In-Depth Information
17. Translation of a regular expression into an NFA is fast and simple. Cre-
ation of an equivalent DFA is slower and can lead to a much larger
automaton. An interesting alternative is to scan using NFAs, thus obvi-
ating the need to ever build a DFA. The idea is to mimic the operation of
the C
routines (as defined in Section 3.8.2)
while scanning. A set of possible states, rather than a single current state,
is maintained. As characters are read, transitions from each state in the
current set are followed, thereby creating a new set of states. If any state
in the current set is final, then the characters read will comprise a valid
token.
Define a suitable encoding for an NFA (perhaps a generalization of the
transition table used for DFAs) and write a scanner driver that can use
this encoding by following the set-of-states approach outlined previ-
ously. This approach to scanning will surely be slower than the standard
approach, which uses DFAs. Under what circumstances is scanning
using NFAs attractive?
lose
and M
ake
D
eterministic
18. Assume
e
is any regular expression.
e
represents the set of all strings not
in the regular set defined by
e
. Show that
e
is a regular set.
Hint
:If
e
is a regular expression, then there is an FA that recognizes the
set defined by
e
. Transform this FA into one that will recognize
e
.
19. Let
Rev
be the operator that reverses the sequence of characters within
a string. For example,
Rev
(
abc
)
=
cba
.Let
R
be any regular expression.
Rev
(
R
) is the set of strings denoted by
R
, with each string reversed. Is
Rev
(
R
) a regular set? Why or why not?
20. Prove that the DFA constructed by M
in Section 3.8.2
is equivalent to the original NFA. To do so, you must show that an input
string can lead to a final state in the NFA if, and only if, that same string
will lead to a final state in the corresponding DFA.
ake
D
eterministic
21. You have scanned an integer literal into a character bu
er (perhaps
yytext). You now want to convert the string representation of the literal
into numeric (int) form. However, the string may represent a value too
large to be represented in int form. Explain how to convert a string
representation of an integer literal into numeric form with full overflow
checking.
ff
