Java Reference
In-Depth Information
12. Because Fortran generally ignores blanks, a character sequence contain-
ing
n
blanks can be scanned as many as 2
n
di
erent ways. Are each
of these alternatives equally probable? If not, how would you alter
the design you proposed in Exercise 11 to examine the most probable
alternatives first?
ff
13. You are to design the ultimate programming language, “Utopia 2010.”
You have already specified the language's tokens using regular expres-
sions and the language's syntax using a CFG. Now you want to deter-
mine those token pairs that require whitespace to separate them (such as
else a) and those that require extra lookahead during scanning (such as
10.0e-22). Explain how you could use the regular expressions and CFG
to automatically find all token pairs that need special handling.
[
k
]
k
14. Show that the set
{
|
k
≥
1
}
is not regular.
Hint
: Show that no fixed
number of FA states is su
cient to exactly match left and right brackets.
15. Show the NFA that would be created for the following expression using
the techniques of Section 3.8:
(
ab
c
)
(
abc
)
|
Using M
, translate the NFA into a DFA. Using the
techniques of Section 3.8.3, optimize the DFA you created into a minimal
state equivalent.
ake
D
eterministic
16. Consider the following regular expression:
1)
0(0
(0
|
|
1)(0
|
1)(0
|
1)
...
(0
|
1)
Display the NFA corresponding to this expression. Show that the equiv-
alent DFA is
exponentially
bigger than the NFA you presented.
