Due date Nov.26.
1. From text: problem 5.3 (p.195) a simple PCP example.
2. The undecidability of PCP can be used to show that it is undecidable
whether a CF grammar is ambiguous. Study the outline of the proof (problem 5.19)
and build an instance of PCP (i.e design the dominoes) to verify that a
language with a dangling-else problem (as in the original Algol60) is ambiguous.
3. From text: problem 5.20 (p.196): some two-dimensional problems are easy.
4. Estimate the information complexity of a string of the form 2 ** ( 2 ** n)).
5. Estimate the information complexity of a string of size n that contains
the first n bits in the infinite expansion of a rational number a / b, where
a and b are relatively prime.