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)