Computer Science 4602
Fall 2002
Homework assignment 2

Due: Tues. Sep 17, at the beginning of class.

These exercises are from the text.

1. 1.5(a-c)
2. 1.10
3. 1.12
4. 1.15(a-d)
5. 1.16
6. 1.24

Hint for 1.24. You are ask to show that, if a given language L is regular, then the language L^R of the reversals of all strings in L is also regular. For example, if L is {aab, bbba, ab} then L^R is {baa, abbb, ba}. Your proof should be a constructive existence proof. You can reason either about finite state machines or about regular expressions, since both define the regular languages. How can you modify a finite state machine to accept the reversals of what it used to accept, or modify a regular expression to describe the reversals of what it used to describe?