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:

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,316 answers

198,360 comments

105,087 users