Due: Tues, Sep 24 at the beginning of class.
These exercises are from the text.
Page 86, ex. 1.17. But do not use the pumping lemma. Show that these languages are not regular using the method that we used in class.
Page 89, ex. 1.31. (Hint: show how to convert an all-paths NFA into a DFA.)
Hint for 1.24. You are ask to show that, if a given language L is regular, then the language LR of the reversals of all strings in L is also regular. For example, if L is {aab, bbba, ab} then LR 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?