search
Log In
0 votes
66 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 undecidable whether or not a CFG generates a regular language. Hint: Suppose there is a solution to PCP; say the string $wx$ is missing from $\overline{L_A}\cup \overline{L_B}$ where  $w$ is a string from the alphabet $\Sigma$ of this PCP instance, and $x$ is the reverse of the corresponding string of index symbols. Define a homomorphism $h(0) = w$ and $h(1) = x.$ Then what is  $h^{-1}(\overline{L_A}\cup \overline{L_B})?$ Use the fact that regular sets are 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.
in Theory of Computation 66 views

Please log in or register to answer this question.

Related questions

1 vote
0 answers
1
116 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 ... $7.2.5(b)$.
asked Jul 26, 2019 in Theory of Computation Lakshman Patel RJIT 116 views
0 votes
0 answers
2
23 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 23 views
0 votes
0 answers
3
13 views
Give an algorithm to tell for two regular languages $L_{1}$ and $L_{2}$ over the same alphabet $\sum,$ whether there is any string in $\sum^{*}$ that is in neither $L_{1}$ nor $L_{2}.$
asked Apr 6, 2019 in Theory of Computation Lakshman Patel RJIT 13 views
...