Constructing PDA for a language I want to prove or disprove that for a given two PDA's (Pushdown Automata) $M_1$ and $M_2$, we can build a PDA $M$ such that 
$$L(M) = \{w \in L(M_1) \mid w\text{ contains some string in }L(M_2)\text{ as substring} \}.$$
 A: This shouldn't be possible. 
Hint: Consider the following two context-free languages over the alphabet $\{ \mathtt{a},\mathtt{b},\mathtt{c},\mathtt{d} \}$:


*

*$L_1 = \{ \mathtt{a}^n\mathtt{b}^n\mathtt{c}^k\mathtt{d} : n,k \geq 1 \}$;

*$L_2 = \{ \mathtt{a}\mathtt{b}^\ell\mathtt{c}^\ell\mathtt{d} : \ell \geq 1 \}$.


Now identify the language $$L = \{ w \in L_1 : w\text{ has a substring which is in }L_2 \}.$$
(That is, if $\mathtt{a}^n\mathtt{b}^n\mathtt{c}^k\mathtt{d}$ ($n,k \geq 1$) has a substring of the form $\mathtt{a}\mathtt{b}^\ell\mathtt{c}^\ell\mathtt{d}$ ($\ell \geq 1$) what can we say about these integers?)

In a bit more generality, suppose that $L_1$ and $L_2$ are two context-free languages over an alphabet $\Sigma$.  Taking a symbol $\mathtt{\#}$ not in $\Sigma$ consider the following context-free languages over $\Sigma \cup \{ \mathtt{\#} \}$:
$$L_1^\prime = \{ \mathtt{\#}u\mathtt{\#} : u \in L_1 \}; \quad L_2^\prime = \{ \mathtt{\#}v\mathtt{\#} : v \in L_2 \}.$$
Now identify the language $$L = \{ w \in L_1^\prime : w\text{ has a substring which is in }L^\prime_2 \}.$$
