Convertir una CFG a un NPDA de estado unico que acepte por pila vacia

La intuicion: el PDA simula la derivacion izquierda en la pila

La conversion de una CFG a un NPDA de un solo estado es una receta mecanica. La idea es que la pila del PDA simula la derivacion izquierda de la gramatica. El simbolo inicial de la pila es $S$ (la variable inicial de la gramatica), y el PDA tiene dos tipos de movimientos: si el tope de la pila es una variable, elige no deterministicamente una produccion y la reemplaza; si el tope es un terminal, lo empareja con el siguiente simbolo de la entrada y lo desapila.

En este problema, la gramatica tiene producciones $S \to 0S1 \mid A$ y $A \to 1A0 \mid S \mid \varepsilon$. Cada una se convierte en una $\varepsilon$-transicion que reemplaza la variable del tope por el lado derecho de la produccion. Ademas, agregamos transiciones para emparejar los terminales $0$ y $1$. El PDA acepta cuando la pila queda vacia (lo que corresponde a que la derivacion genero exactamente la cadena de entrada).

Lo elegante es que con un unico estado y las transiciones correctas, el no determinismo del PDA explora todas las derivaciones posibles. Si alguna genera la cadena de entrada, el PDA la encuentra.

Gramatica

$$\begin{aligned} S &\to 0S1 \mid A \\ A &\to 1A0 \mid S \mid \varepsilon \end{aligned}$$

NPDA de estado unico — Pila vacia

$M = (\{q\}, \{0, 1\}, \{S, A, 0, 1\}, \delta, q, S)$

Transiciones

Producciones:

$$\begin{aligned} \delta(q, \varepsilon, S) &= \{(q, 0S1),\; (q, A)\} \\ \delta(q, \varepsilon, A) &= \{(q, 1A0),\; (q, S),\; (q, \varepsilon)\} \end{aligned}$$

Emparejamiento de terminales:

$$\begin{aligned} \delta(q, 0, 0) &= \{(q, \varepsilon)\} \\ \delta(q, 1, 1) &= \{(q, \varepsilon)\} \end{aligned}$$

Traza: $01$

$$\begin{aligned} (q, 01, S) &\vdash (q, 01, 0S1) &\quad S \to 0S1 \\ &\vdash (q, 1, S1) &\quad \text{emparejar } 0 \\ &\vdash (q, 1, A1) &\quad S \to A \\ &\vdash (q, 1, 1) &\quad A \to \varepsilon \\ &\vdash (q, \varepsilon, \varepsilon) &\quad \text{emparejar } 1 \quad \checkmark \end{aligned}$$

Traza: $\varepsilon$

$$\begin{aligned} (q, \varepsilon, S) &\vdash (q, \varepsilon, A) &\quad S \to A \\ &\vdash (q, \varepsilon, \varepsilon) &\quad A \to \varepsilon \quad \checkmark \end{aligned}$$

Automata

Solucion

Metodo: Conversion estandar de CFG a NPDA

La conversion estandar de una CFG $G = (N, \Sigma, P, S)$ a un NPDA de un solo estado $q$ que acepta por pila vacia funciona asi:

1. El NPDA tiene un unico estado $q$.
2. El alfabeto de pila es $\Gamma = N \cup \Sigma$.
3. El simbolo inicial de pila es $S$.
4. Para cada produccion $A \to \alpha$ en la gramatica, anadimos la transicion: $\delta(q, \varepsilon, A) \ni (q, \alpha)$ (si $\alpha = \varepsilon$, se desapila $A$).
5. Para cada terminal $a \in \Sigma$, anadimos: $\delta(q, a, a) = \{(q, \varepsilon)\}$ (emparejar terminal).

Gramatica dada

$$\begin{aligned} S &\to 0S1 \mid A \\ A &\to 1A0 \mid S \mid \varepsilon \end{aligned}$$

NPDA resultante

$M = (\{q\}, \{0, 1\}, \{S, A, 0, 1\}, \delta, q, S)$

Acepta por pila vacia.

Transiciones

Producciones de la gramatica (reemplazo en la pila):

$$\begin{aligned} \delta(q, \varepsilon, S) &= \{(q, 0S1), (q, A)\} &\quad \text{(de } S \to 0S1 \mid A\text{)} \\ \delta(q, \varepsilon, A) &= \{(q, 1A0), (q, S), (q, \varepsilon)\} &\quad \text{(de } A \to 1A0 \mid S \mid \varepsilon\text{)} \end{aligned}$$

Emparejamiento de terminales:

$$\begin{aligned} \delta(q, 0, 0) &= \{(q, \varepsilon)\} \\ \delta(q, 1, 1) &= \{(q, \varepsilon)\} \end{aligned}$$

Nota sobre la notacion de la pila

Cuando escribimos $\delta(q, \varepsilon, S) \ni (q, 0S1)$, el tope de la pila es el simbolo mas a la izquierda del reemplazo. Es decir, se desapila $S$ y se apila $1$, luego $S$, luego $0$ (quedando $0$ en el tope).

Tabla completa de transiciones

Estado	Entrada	Tope pila	Estado siguiente	Reemplazo pila	Regla
$q$	$\varepsilon$	$S$	$q$	$0S1$	$S \to 0S1$
$q$	$\varepsilon$	$S$	$q$	$A$	$S \to A$
$q$	$\varepsilon$	$A$	$q$	$1A0$	$A \to 1A0$
$q$	$\varepsilon$	$A$	$q$	$S$	$A \to S$
$q$	$\varepsilon$	$A$	$q$	$\varepsilon$	$A \to \varepsilon$
$q$	$0$	$0$	$q$	$\varepsilon$	emparejar $0$
$q$	$1$	$1$	$q$	$\varepsilon$	emparejar $1$

Verificacion interactiva

Traza para la cadena $01$:

Verificacion: cadena $01$

La cadena $01$ se deriva en la gramatica como:

$S \Rightarrow 0S1 \Rightarrow 0A1 \Rightarrow 0\varepsilon1 = 01$

Traza del NPDA para la cadena $01$:

Paso	Configuracion $(q, \text{entrada}, \text{pila})$	Regla
0	$(q, 01, S)$	Inicio
1	$(q, 01, 0S1)$	$S \to 0S1$
2	$(q, 1, S1)$	emparejar $0$
3	$(q, 1, A1)$	$S \to A$
4	$(q, 1, 1)$	$A \to \varepsilon$
5	$(q, \varepsilon, \varepsilon)$	emparejar $1$

Pila vacia, entrada consumida: acepta $\checkmark$

Traza para la cadena vacia $\varepsilon$

Paso	Configuracion	Regla
0	$(q, \varepsilon, S)$	Inicio
1	$(q, \varepsilon, A)$	$S \to A$
2	$(q, \varepsilon, \varepsilon)$	$A \to \varepsilon$

Pila vacia: acepta $\checkmark$ (ya que $\varepsilon$ esta en el lenguaje generado por la gramatica)