Assignment II

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.