Proponer un NPDA para el lenguaje {0^n 1^m | m = 3n, n > 0}

La intuicion: apilar 3 marcas por cada 0

El lenguaje pide que por cada $0$ haya exactamente tres $1$‘s. La pila es perfecta para esto: por cada $0$ que leemos, apilamos 3 marcas. Despues, por cada $1$ que leemos, desapilamos 1 marca. Si al final la pila queda vacia, hubo exactamente $3n$ unos para $n$ ceros.

En la practica, la primera vez que vemos un $0$ apilamos $XXX$ sobre $Z_0$. Para cada $0$ adicional, necesitamos agregar 3 $X$‘s mas, pero la transicion del PDA siempre opera sobre el tope: lee un $X$, y lo reemplaza por $XXXX$ (remueve 1, agrega 4 = neto +3). Luego pasamos a leer $1$‘s, y cada una simplemente desapila un $X$.

El automata es deterministico en la practica (aunque lo llamemos NPDA): no hay ambiguedad en que hacer en cada paso. La condicion $n > 0$ se garantiza teniendo un estado inicial separado que solo transiciona al leer el primer $0$; si no hay ceros, el automata nunca llega al estado de aceptacion.

NPDA

$M = (\{q_0, q_1, q_2, q_f\}, \{0, 1\}, \{X, Z_0\}, \delta, q_0, Z_0, \{q_f\})$

Acepta por estado final.

Transiciones

$$\begin{aligned} \delta(q_0, 0, Z_0) &= \{(q_1, XXXZ_0)\} \\ \delta(q_1, 0, X) &= \{(q_1, XXXX)\} \\ \delta(q_1, 1, X) &= \{(q_2, \varepsilon)\} \\ \delta(q_2, 1, X) &= \{(q_2, \varepsilon)\} \\ \delta(q_2, \varepsilon, Z_0) &= \{(q_f, \varepsilon)\} \end{aligned}$$

Traza: $0111$

$$\begin{aligned} (q_0, 0111, Z_0) &\vdash (q_1, 111, XXXZ_0) \\ &\vdash (q_2, 11, XXZ_0) \\ &\vdash (q_2, 1, XZ_0) \\ &\vdash (q_2, \varepsilon, Z_0) \\ &\vdash (q_f, \varepsilon, \varepsilon) \quad \checkmark \end{aligned}$$

Traza: $00111111$

$$\begin{aligned} (q_0, 00111111, Z_0) &\vdash (q_1, 0111111, XXXZ_0) \\ &\vdash (q_1, 111111, XXXXXXZ_0) \\ &\vdash (q_2, 11111, XXXXXZ_0) \\ &\vdash \cdots \vdash (q_2, \varepsilon, Z_0) \\ &\vdash (q_f, \varepsilon, \varepsilon) \quad \checkmark \end{aligned}$$

Automata

Solucion

Analisis del lenguaje

El lenguaje es $L = \{0^n 1^m \mid m = 3n \land n > 0\}$.

Cada $0$ debe corresponder a exactamente tres $1$‘s. Ejemplos: $0111$, $00111111$, $000111111111$.

Idea

Por cada $0$ leido, apilamos 3 marcas. Luego, por cada $1$ leido, desapilamos una marca. Al final, la pila debe estar vacia (excepto por el simbolo de fondo).

Definicion formal

$M = (\{q_0, q_1, q_2, q_f\}, \{0, 1\}, \{X, Z_0\}, \delta, q_0, Z_0, \{q_f\})$

El automata acepta por estado final.

Transiciones

$$\begin{aligned} \delta(q_0, 0, Z_0) &= \{(q_1, XXXZ_0)\} &\quad \text{primera } 0\text{: apilar 3 } X\text{'s} \\ \delta(q_1, 0, X) &= \{(q_1, XXXX)\} &\quad \text{cada } 0 \text{ adicional: reemplazar tope por 4 } X\text{'s (neto +3)} \\ \delta(q_1, 1, X) &= \{(q_2, \varepsilon)\} &\quad \text{primera } 1\text{: empezar a desapilar} \\ \delta(q_2, 1, X) &= \{(q_2, \varepsilon)\} &\quad \text{cada } 1 \text{: desapilar un } X \\ \delta(q_2, \varepsilon, Z_0) &= \{(q_f, \varepsilon)\} &\quad \text{pila vacia: aceptar} \\ \end{aligned}$$

Explicacion

1. Estado $q_0$: Estado inicial. Al leer el primer $0$, apilamos $XXX$ sobre $Z_0$ y vamos a $q_1$. Esto garantiza $n > 0$.
2. Estado $q_1$: Leyendo $0$‘s. Por cada $0$, desapilamos el tope $X$ y apilamos $XXXX$ (incremento neto de 3 $X$‘s). Al leer el primer $1$, desapilamos un $X$ y pasamos a $q_2$.
3. Estado $q_2$: Leyendo $1$‘s. Por cada $1$, desapilamos un $X$. Cuando la pila solo tiene $Z_0$, hacemos $\varepsilon$-transicion a $q_f$.
4. Estado $q_f$: Estado de aceptacion.

Despues de leer $n$ ceros, la pila tiene $3n$ marcas $X$ (mas $Z_0$). Despues de leer $m$ unos, se desapilan $m$ marcas. El automata acepta cuando $m = 3n$ y la pila queda solo con $Z_0$.

Verificacion interactiva

Traza para $0111$:

Traza para $00111111$:

Verificacion: cadena $0111$

Paso	Estado	Entrada restante	Pila	Accion
0	$q_0$	$0111$	$Z_0$	Inicio
1	$q_1$	$111$	$XXXZ_0$	Leer $0$: apilar $XXX$
2	$q_2$	$11$	$XXZ_0$	Leer $1$: desapilar $X$
3	$q_2$	$1$	$XZ_0$	Leer $1$: desapilar $X$
4	$q_2$	$\varepsilon$	$Z_0$	Leer $1$: desapilar $X$
5	$q_f$	$\varepsilon$	$\varepsilon$	$\varepsilon$-transicion: aceptar

Acepta $\checkmark$

Verificacion: cadena $00111111$

Paso	Estado	Entrada restante	Pila	Accion
0	$q_0$	$00111111$	$Z_0$	Inicio
1	$q_1$	$0111111$	$XXXZ_0$	Leer $0$: apilar 3 $X$‘s
2	$q_1$	$111111$	$XXXXXXZ_0$	Leer $0$: apilar 3 $X$‘s mas
3	$q_2$	$11111$	$XXXXXZ_0$	Leer $1$: desapilar $X$
4-7	$q_2$	$\cdots$	$\cdots$	Continuar desapilando
8	$q_2$	$\varepsilon$	$Z_0$	Todas las $X$ desapiladas
9	$q_f$	$\varepsilon$	$\varepsilon$	Aceptar

Acepta $\checkmark$