1
$\begingroup$

Is "Given a CFL L and a regular language R, is intersection of L and R an empty set?" decidable? What if we replace L with the complement of L? One of them is decidable and the other is not. For the one that is decidable, give an algorithm. For the other, give an undecidability proof.

For the first part "Given a CFL L and a regular language R, is intersection of L and R an empty set?", I have the following idea. I think it is decidable because an intersection of context-free language and regular language is context-free, and then we can build context-free grammar G from the langauge. For a given CFG G, checking whether the language(G) is empty or not is decidable.

But I have one thing that I'm not sure of. For given context-free language, how can a Turing machine build context-free grammar? As far as I know, there is no known procedure for doing this. If there is no general procedure for building context-free grammar, I think the above proof is invalid.

But I read a proof of theorem "Every context-free language is decidable" from Sipser textbook, and the proof says that for any arbitrary CFL A, we build a grammar G that recognizes A, and we have to include this description of G into our machine. I guess this could work because CFL is fixed, but the above machine needs to take any arbitrary CFL L and regular language R.

$\endgroup$
1
  • $\begingroup$ "For given context-free language, how can a Turing machine build context-free grammar?" Well, if you don't have a context-free grammar, what does the expression "a given context-free language" mean. In other words, what would be the input of your Turing machine if the context-free language is not given by a grammar? If you use pushdown automata, they can be converted into grammars. $\endgroup$
    – J.-E. Pin
    May 24 at 14:21
1
$\begingroup$

It is known that the intersection of a regular language and a context free one is context free. Besides, you can always take your regular language to be $\Sigma^*$, so any context free language can be the result.

Then the question is if a given context free language is empty, which is easy to answer.

To ask if the complement of a context free language is empty is to ask if it is $\Sigma^*$, which is undecidable.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.