Complexity of intersection of regular languages as context-free grammars Given regular expressions $R_1, \dots, R_n$, are there any non-trivial bounds on the size of the smallest context-free grammar for $R_1 \cap \cdots \cap R_n$?
This is a great question and it really lies within my interests.  I'm glad that you asked it Max.

Let $n$ DFA's with at most $O(n)$ states each be given.  It would be nice if there existed a PDA with sub-exponentially many states that accepts the intersection of the DFA's languages.  However, I suggest that such a PDA might not always exist.

Consider the copy language.  Now, restrict it to copying strings of length n.

Formally, consider $n$-copy $:=$ $\{ xx \, | \, x \in \{0,1\}^{n}\}$.

We can represent $n$-copy as the intersection of $n$ DFA's of size at most $O(n)$.  However, the smallest DFA that accepts $n$-copy has $2^{\Omega(n)}$ states.

Similarly, if we restrict ourselves to a binary stack alphabet, then I suspect that the smallest PDA that accepts $n$-copy has exponentially many states.

P.S.  Feel free to send me an email if you would like to discuss further.  :)