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.


Your Answer

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

Browse other questions tagged or ask your own question.