CS395: Some algorithms

Due: 12:30PM Wednesday, February 18

1. (Algorithm 3.3 -- from regular expression to NFA.) Do problem 3.16 on page 149, parts (b) and (d).

2. (Algorithm 3.2 -- from NFA to DFA.) Do problem 3.17, parts (b) and (d).

3. (Algorithm 3.5 -- from regular expression directly to DFA.) Do problem 3.18, parts (b) and (d).

4. (Algorithm 3.6 -- minimizing the states of a DFA.) Do problem 3.21, parts (b) and (d).

5. (Building shift-reduce parsing tables.) Do problem 4.35 on page 272, parts (a) and (b).

6. (The difference between SLR(1) and LALR(1).) Do problem 4.39.