Honors Compilers
HW 1 - due Tues. Feb. 5
Lexical Analysis
1. Show that regular expressions (a | b) * , (a* | b* )* , and
((lambda | a ) b * ) * are equivalent, because their minstate DFA's are
the same, except for state names.
2. Prove that any DFA for regular expression (a | b)* a (a | b)...(a | b),
where there are n-1 (a | b)'s at the end, must have at least 2**n states.
3. Consider the regular expression R = (a | b)* abb
Compute I sup T, F sup T, lazynred, null, and lazydelta sup T for each
subexpression of R. What is I sub R, F sub R, and lazydelta sub R, and
describe the data structure to implement it.
4. What is the DFA that results from applying Rabin/Scott subset construction
to your NFA from (3.)? Show the subset of NFA states corresponding to each of
your DFA states.
5. Problem 8 in Chapt. 7 of W/M book.
6. Problem 10 in Chapt. 7 of W/M book. (correction: use the dfa produced
in ex. 8; use the table compression technique of sec. 7.4.3)