What is the complexity of deciding if the intersection of a regular language and a context free language is empty?

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?

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

StackExchange Computer Science Q#80713, answer score: 4