Due date Sep. 23.
1. From text: exercises 1.4 parts a, c, g, l, n.
2. For each of the above, give the regular expression corresponding
to each of the languages.
3. From text: exercise 1.12: convert the DFA's into regular expressions.
4. From text: exercise 1.15 parts a, e, h.
5. We define the reversal operation R (s) on a string s as the string obtained
by listing its constituent symbols in reverse order. Similarly, we define
the reversal of a language R (L) as the set of reversals of all the strings
in L. Prove as precisely as possible that if L is a regular language then
R (L) is also regular.
6. (Optional) The firing squad synchronization problem (also known as the
Rockettes problem) as described in class.