Assignment VI

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.