search
Log In
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}.$
  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 159 views

Please log in or register to answer this question.

Related questions

0 votes
0 answers
1
95 views
Show that the language $\overline{L_A}\cup \overline{L_B}$ is a regular language if and only if it is the set of all strings over its alphabet;i.e., if and only if the instance $(A,B)$ of PCP has no solution. Thus, prove that it is ... closed under inverse homomorphism, complementation and the pumping lemma for regular sets to show that $\overline{L_A}\cup \overline{L_B}$ is not regular.
asked Jul 26, 2019 in Theory of Computation Lakshman Patel RJIT 95 views
0 votes
0 answers
2
60 views
Let $L$ be the set of (codes for) context-free grammars $G$ such that $L(G)$ contains at least one palindrome. Show that $L$ is undecidable. Hint: Reduce PCP to $L$ by constructing, from each instance of PCP a grammar whose language contains a palindrome if and only if the PCP instance has a solution.
asked Jul 26, 2019 in Theory of Computation Lakshman Patel RJIT 60 views
0 votes
0 answers
3
53 views
The $\text{shuffle}$ of two strings $w$ and $x$ is the set of all strings that one can get by interleaving the positions of $w$ and $x$ in any way. More precisely $,\text{shuffle(w,x)}$ is the set of strings $z$ such that Each position of $z$ can be assigned to $w$ or $x,$but not ... to show that if $L_{1}$ and $L_{2}$ are both $CFL's,$ then $\text{shuffle($L_{1},L_{2}$)}$ need not be a $CFL.$
asked Apr 11, 2019 in Theory of Computation Lakshman Patel RJIT 53 views
0 votes
0 answers
4
32 views
There is a stronger version of the $CFL$ pumping lemma known as Ogden's lemma.It differs from the pumping lemma we proved by allowing us to focus on any $n$ $"$distinguished$"$ positions of a string $z$ and guaranteeing that the strings to be pumped have between $1$ ... if we pretend that the non-distinguished positions of $z$ are not present as we select a long path in the parse tree for $z.$
asked Apr 11, 2019 in Theory of Computation Lakshman Patel RJIT 32 views
...