1 vote

It is undecidable whether the complement of a CFL is also a CFL. Exercise $9.5.2$ can be used to show it is undecidable whether the complement of a CFL is regular, but that is not the same thing. To prove our initial claim, we need to define a different language that represents the nonsolutions to an instance $(A, B)$ of PCP. Let $L_{AB}$ be the set of strings of the form $w\#x\#y\#z$ such that:

- $w$ and $x$ are strings over the alphabet $\Sigma$ of the PCP instance.
- $y$ and $z$ are strings over the index alphabet $I$ for this instance.
- $\#$ is a symbol in neither $\Sigma$ nor $I$.
- At least one of the following holds:

- $w\neq x^{R}.$
- $y\neq z^{R}.$
- $x^{R}$ is not what the index string $y$ generates according to list $
- $w$ is not what the index string $z^{R}$ generates according to the list $A$.

Notice that $L_{AB}$ consists of all strings in $\Sigma^{\ast}\#\Sigma^{\ast}\#I^{\ast}$ unless the instance $(A B)$ has a solution, but $L_{AB}$ is a CFL regardless. Prove that $L_{AB}$ is a CFL if and only if there is no solution. Hint: Use the inverse homomorphism trick from Exercise $9.5.2$ and use Ogden's lemma to force equality in the lengths of certain substrings as in the hint to Exercise $7.2.5(b)$.