Construir una PDA para una lengua

Question

Quiero probar ou refutar que para dos PDA's dados (Autómatas Pushdown) $M_1$ y $M_2$ podemos construir una PDA $M$ tal que

$$L(M) = \{w \in L(M_1) \mid w\text{ contains some string in }L(M_2)\text{ as substring} \}.$$

Answer 1

Esto no debería ser posible.

Una pista: Consideremos los siguientes dos lenguajes libres de contexto sobre el alfabeto $\{ \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 \}$ .

Ahora identifique la lengua $$L = \{ w \in L_1 : w\text{ has a substring which is in }L_2 \}.$$

(Es decir, si $\mathtt{a}^n\mathtt{b}^n\mathtt{c}^k\mathtt{d}$ ( $n,k \geq 1$ ) tiene una subcadena de la forma $\mathtt{a}\mathtt{b}^\ell\mathtt{c}^\ell\mathtt{d}$ ( $\ell \geq 1$ ) ¿qué podemos decir de estos enteros?)

---

Con un poco más de generalidad, supongamos que $L_1$ y $L_2$ son dos lenguajes libres de contexto sobre un alfabeto $\Sigma$ . Tomar un símbolo $\mathtt{\#}$ no en $\Sigma$ consideremos los siguientes lenguajes libres de contexto sobre $\Sigma \cup \{ \mathtt{\#} \}$ :

$$L_1^\prime = \{ \mathtt{\#}u\mathtt{\#} : u \in L_1 \}; \quad L_2^\prime = \{ \mathtt{\#}v\mathtt{\#} : v \in L_2 \}.$$

Ahora identifique la lengua $$L = \{ w \in L_1^\prime : w\text{ has a substring which is in }L^\prime_2 \}.$$