The Gateway to Computer Science Excellence
+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:

  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)$.

in Theory of Computation by Veteran (59k points) | 88 views

Please log in or register to answer this question.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,316 answers
105,087 users