# Ullman (TOC) Edition 3 Exercise 9.5 Question 3 (Page No. 418 - 419)

1 vote
159 views

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:

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

1. $w\neq x^{R}.$
2. $y\neq z^{R}.$