COMS W3261 CS Theory
Lecture 17: Post's Correspondence Problem

1. Complements of Ld and Lu

2. Post's Correspondence Problem (PCP)

3. Modified PCP

4. Reducing the Universal Language to MPCP

5. Undecidability of the Ambiguity Problem for CFG's

6. Practice Problems

  1. Does the following instance of PCP have a solution: A = (ab, aab, ba) and B = (abb, ba, aa)?
  2. Does the following instance of PCP have a solution: A = (ab, b, aba, aa) and B = (abab, a, b, a)?
  3. Does the following instance of PCP have a solution: A = (ab, baa, aba) and B = (aba, aa, baa)?
  4. Is PCP on lists over a single-symbol alphabet decidable?
  5. Show that the PCP problem can be formulated as a language recognition problem.

7. Reading


aho@cs.columbia.edu
verma@cs.columbia.edu