The Gateway to Computer Science Excellence
0 votes
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 by Veteran (58.6k points) | 34 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,741 questions
57,251 answers
104,671 users