A printable PDF is available.

Assignment 4: Due Thursday, October 16

1. Page 211, Problem 5.13.
2. Page 184, Problem 4.22 (Yes, this is from Chapter 4 - that's not a typo. It's related to the problem 5.13, so this is a good time to think about it!)
3. Page 212, Problem 5.14
4. Page 212, Problem 5.15
5. Page 212, Problem 5.20
6. Page 212, Problem 5.22
7. Page 212, Problem 5.23

The following problem is a "challenge problem" -- you are not required to do it, but if you get a good solution you will receive extra credit (up to 10 points).

1. Define REVERSIBLE_CFG={ < G > |G is a CFG and L(G)=L(G)^R} (recall that L^R means the language consisting of the reversal of all strings in L). Show that the language REVERSIBLE_CFG is undecidable.