Demostrar que L(M) = L(G) usando equivalencia entre derivacion y configuraciones del PDA

La intuicion: cada paso de derivacion es un paso del PDA y viceversa

Nos dan un lema que dice que derivar en la gramatica es lo mismo que computar en el PDA: cada paso de derivacion izquierda $A \Rightarrow z\gamma$ corresponde exactamente a un paso de computacion $(q, zy, A) \vdash (q, y, \gamma)$. La demostracion de $L(M) = L(G)$ es usar ese lema en ambas direcciones.

Para ver que $L(G) \subseteq L(M)$: si una cadena $w$ esta en el lenguaje de la gramatica, hay una derivacion $S \Rightarrow^* w$. El lema traduce esa derivacion en una computacion del PDA que arranca con $w$ en la entrada y $S$ en la pila, y termina con entrada y pila vacias. Eso es exactamente aceptar por pila vacia.

Para ver que $L(M) \subseteq L(G)$: si el PDA acepta $w$, hay una computacion que vacia la pila. El lema en la direccion inversa traduce esa computacion en una derivacion $S \Rightarrow^* w$ en la gramatica. Ambas inclusiones juntas dan la igualdad $L(M) = L(G)$.

Lema (dado)

$\forall\, z,y \in \Sigma^*,\; \gamma \in N^*,\; A \in N: \quad A \xRightarrow[G]{n} z\gamma \;\;\text{(izq.)} \iff (q, zy, A) \xRightarrow[M]{n} (q, y, \gamma)$

Parte 1: $L(G) \subseteq L(M)$

Sea $w \in L(G)$. Entonces $\exists\, n$:

$S \xRightarrow[G]{n} w \quad \text{(derivacion izquierda)}$

con $w \in \Sigma^*$. Tomando $A = S$, $z = w$, $\gamma = \varepsilon$, $y = \varepsilon$ en el lema ($\Rightarrow$):

$S \xRightarrow[G]{n} w\varepsilon \;\implies\; (q, w, S) \xRightarrow[M]{n} (q, \varepsilon, \varepsilon)$

$M$ acepta $w$ por pila vacia. $\therefore\; w \in L(M)$.

Parte 2: $L(M) \subseteq L(G)$

Sea $w \in L(M)$. Entonces $\exists\, n$:

$(q, w, S) \xRightarrow[M]{n} (q, \varepsilon, \varepsilon)$

Tomando $A = S$, $z = w$, $\gamma = \varepsilon$, $y = \varepsilon$ en el lema ($\Leftarrow$):

$(q, w, S) \xRightarrow[M]{n} (q, \varepsilon, \varepsilon) \;\implies\; S \xRightarrow[G]{n} w$

$\therefore\; w \in L(G)$.

Conclusion

$L(G) \subseteq L(M) \;\wedge\; L(M) \subseteq L(G) \;\implies\; L(M) = L(G) \quad \blacksquare$

Automata

Solucion

Contexto

Dada una gramatica libre de contexto $G = (N, \Sigma, P, S)$, el NPDA $M$ construido a partir de $G$ (conversion estandar) tiene un solo estado $q$, acepta por pila vacia, y usa $\Gamma = N \cup \Sigma$ como alfabeto de pila con $S$ como simbolo inicial.

La gramatica $G$

El NPDA $M$ construido a partir de $G$

Se nos da el siguiente lema (sin demostracion):

Lema: Para cualquier $z, y \in \Sigma^*$, $\gamma \in N^*$, y $A \in N$:

$A \xRightarrow[G]{n} z\gamma \text{ (por derivacion izquierda)} \iff (q, zy, A) \xRightarrow[M]{n} (q, y, \gamma)$

Demostracion de $L(M) = L(G)$

Debemos mostrar dos inclusiones.

Parte 1: $L(G) \subseteq L(M)$

Sea $w \in L(G)$. Entonces existe una derivacion:

$S \xRightarrow[G]{*} w$

Toda derivacion en una CFG puede reordenarse como una derivacion por la izquierda (propiedad fundamental de las CFG). Por lo tanto existe $n$ tal que:

$S \xRightarrow[G]{n} w \quad \text{(derivacion por la izquierda)}$

Aqui $w \in \Sigma^*$ es una cadena de terminales, asi que podemos escribir $w = z\gamma$ donde $z = w$ y $\gamma = \varepsilon$ (cadena vacia de no terminales, ya que $w$ no contiene no terminales).

Aplicando el lema con $A = S$, $z = w$, $\gamma = \varepsilon$, y eligiendo $y = \varepsilon$:

$S \xRightarrow[G]{n} w\varepsilon = w \implies (q, w\varepsilon, S) \xRightarrow[M]{n} (q, \varepsilon, \varepsilon)$

Es decir:

$(q, w, S) \xRightarrow[M]{n} (q, \varepsilon, \varepsilon)$

El PDA $M$ empieza con la entrada $w$, el simbolo de pila $S$, y llega a una configuracion con entrada consumida y pila vacia. Por lo tanto, $M$ acepta $w$ por pila vacia.

Luego $w \in L(M)$. $\checkmark$

Parte 2: $L(M) \subseteq L(G)$

Sea $w \in L(M)$. Entonces el PDA $M$ acepta $w$ por pila vacia, es decir:

$(q, w, S) \xRightarrow[M]{*} (q, \varepsilon, \varepsilon)$

Esto significa que existe $n$ tal que:

$(q, w, S) \xRightarrow[M]{n} (q, \varepsilon, \varepsilon)$

Aplicando el lema en la direccion inversa ($\Leftarrow$) con $A = S$, $y = \varepsilon$, $\gamma = \varepsilon$, y $z = w$:

$(q, w\varepsilon, S) \xRightarrow[M]{n} (q, \varepsilon, \varepsilon) \implies S \xRightarrow[G]{n} w\varepsilon = w \quad \text{(derivacion izquierda)}$

Por lo tanto, $S \xRightarrow[G]{*} w$, lo que significa que $w \in L(G)$. $\checkmark$

Conclusion

$L(G) \subseteq L(M) \text{ y } L(M) \subseteq L(G) \implies L(M) = L(G)$

$\blacksquare$

Verificacion interactiva

Para ilustrar la correspondencia, veamos como $M$ procesa la cadena $01$:

Observacion

La clave de esta demostracion es el lema que establece una correspondencia biyectiva entre los pasos de derivacion izquierda en $G$ y los pasos de computacion en $M$. Esto refleja la construccion del NPDA: cada transicion del PDA simula exactamente un paso de derivacion izquierda de la gramatica.