3
$\begingroup$

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?

$\endgroup$
  • $\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
3
$\begingroup$

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).

$\endgroup$
  • $\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
  • $\begingroup$ I don't understand the claim " Beigel and Gasarch show how to compute a CFG for the intersection in polynomial time" if the regular language is given as an NFA. They seem to assume a DFA as input, and they don't mention polynomial time at all. $\endgroup$ – a3nm Mar 15 at 18:05
  • $\begingroup$ If memory serves, their construction works for NFAs as well, and furthermore is quite efficient, and in particular can be implemented in polytime (even if they don’t mention it). $\endgroup$ – Yuval Filmus Mar 15 at 18:37

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.