Constructing PDA for a language

Question

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} \}.$$

Answer 1

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 \}.$$