A printable PDF is available.

## Assignment 4: Due Thursday, October 16

- Page 211, Problem 5.13.
- 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!)
- Page 212, Problem 5.14
- Page 212, Problem 5.15
- Page 212, Problem 5.20
- Page 212, Problem 5.22
- 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).

- Define
*REVERSIBLE*is a CFG and_{CFG}={ < G > |G*L(G)=L(G)*} (recall that^{R}*L*means the language consisting of the reversal of all strings in^{R}*L*). Show that the language*REVERSIBLE*is undecidable._{CFG}