+1 vote
88 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}.$
3. $x^{R}$ is not what the index string $y$ generates according to list $4.$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)\$.

| 88 views