Let's say we have a context free language, the CFG that produces it.

And then we have a DFA for a regular language.

If the intersection is empty is decidable, but how and how efficiently?

And if you could be so kind, please explain the best known algorithm as simple as you can?

  • $\begingroup$ Please note that the entire question should be understandable from its body. $\endgroup$ – Yuval Filmus Sep 1 '17 at 11:33
  • $\begingroup$ @YuvalFilmus Thank you, I made my edits to fix this. $\endgroup$ – Askeroni Sep 1 '17 at 11:52

The answer depends on how the two languages are given to you; I will assume that the context-free language is given as a CFG, and that the regular language is given as a DFA/NFA. Beigel and Gasarch show how to compute a CFG for the intersection in polynomial time. You can then check whether the resulting language is empty using grammar simplification (described in any decent textbook).

  • $\begingroup$ Is there no way without merging the two first? Just curious. $\endgroup$ – Askeroni Sep 1 '17 at 11:54
  • $\begingroup$ Not that I am aware of. $\endgroup$ – Yuval Filmus Sep 1 '17 at 12:30

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.