# Bounded non-emptiness intersection of deterministic context-free grammars

Let A and B be two determinstic context-free grammar, and let N be an integer: What's the complexity of deciding if the intersection of the languages accepted by A and B over all strings of length less than N is empty?

It's easy to check that the problem is PSPACE-Hard for general CFGs. The reduction can be done from intersection emptiness problem of a set of Deterministic Finite Automata. The proof relies heavily on the unambiguity of the construction though. For Determinstic CFGs, I can't manage to find the solution. We know that the unbounded version of the problem is undecidable, though. This makes me think that the problem is at least NP-Hard. However, I couldn't derive a proof for this.

The theorem holds for non-recursive (deterministic) CF grammars, so your problem is simply a generalization: using the same construction, just set $$N$$ large enough to include the longest string (i.e. the max number of steps of the "simulated" LBA).