Disenar un PDA para el lenguaje {a^n b^m c^k | k = |n - m|}

La intuicion: la pila lleva la cuenta del desbalance

El lenguaje pide cadenas $a^n b^m c^k$ donde $k$ es la diferencia absoluta entre $n$ y $m$. Es decir, las $c$‘s compensan lo que sobre de $a$‘s o de $b$‘s. Como hay valor absoluto, hay dos casos: que haya mas $a$‘s que $b$‘s, o al reves. Eso nos obliga a usar no determinismo porque el PDA tiene que “adivinar” al inicio cual caso aplica.

La idea central es usar la pila como contador. En el caso $n \geq m$: apilamos una marca por cada $a$, desapilamos una por cada $b$, y lo que quede en la pila lo desapilamos con las $c$‘s. En el caso $n < m$: tambien apilamos por cada $a$, desapilamos con las $b$‘s, pero cuando se acaban las marcas de $a$‘s empezamos a apilar por cada $b$ sobrante, y luego las $c$‘s desapilan esas marcas.

El truco es que el PDA elige no deterministicamente que rama seguir al leer la primera $b$. Si adivina correctamente, la pila queda vacia justo al terminar las $c$‘s y el automata acepta. Si adivina mal, esa rama se atora. Como es no deterministico, con que una rama acepte, la cadena es aceptada.

NPDA

$M = (\{q_0, q_1, q_2, q_3, q_4, q_f\}, \{a, b, c\}, \{X, Z_0\}, \delta, q_0, Z_0, \{q_f\})$

Acepta por estado final.

Transiciones

$$\begin{aligned} \delta(q_0, a, Z_0) &= \{(q_0, XZ_0)\} \\ \delta(q_0, a, X) &= \{(q_0, XX)\} \\ \delta(q_0, b, X) &= \{(q_1, \varepsilon), (q_3, \varepsilon)\} \\ \delta(q_0, b, Z_0) &= \{(q_3, XZ_0)\} \\ \delta(q_0, \varepsilon, Z_0) &= \{(q_f, \varepsilon)\} \\ \delta(q_0, \varepsilon, X) &= \{(q_2, X)\} \\[6pt] \delta(q_1, b, X) &= \{(q_1, \varepsilon)\} \\ \delta(q_1, \varepsilon, X) &= \{(q_2, X)\} \\ \delta(q_1, \varepsilon, Z_0) &= \{(q_f, \varepsilon)\} \\[6pt] \delta(q_2, c, X) &= \{(q_2, \varepsilon)\} \\ \delta(q_2, \varepsilon, Z_0) &= \{(q_f, \varepsilon)\} \\[6pt] \delta(q_3, b, X) &= \{(q_3, \varepsilon)\} \\ \delta(q_3, b, Z_0) &= \{(q_4, XZ_0)\} \\[6pt] \delta(q_4, b, X) &= \{(q_4, XX)\} \\ \delta(q_4, \varepsilon, X) &= \{(q_2, X)\} \end{aligned}$$

Traza: $aabc$ ($n=2, m=1, k=1$)

$$\begin{aligned} (q_0, aabc, Z_0) &\vdash (q_0, abc, XZ_0) \\ &\vdash (q_0, bc, XXZ_0) \\ &\vdash (q_1, c, XZ_0) \\ &\vdash (q_2, c, XZ_0) \\ &\vdash (q_2, \varepsilon, Z_0) \\ &\vdash (q_f, \varepsilon, \varepsilon) \quad \checkmark \end{aligned}$$

Automata

Solucion

Analisis del lenguaje

El lenguaje es $L = \{a^n b^m c^k \mid k = |n - m| \land n \geq 0 \land m \geq 0\}$.

Hay dos casos:

1. $n \geq m$: entonces $k = n - m$, es decir, $k + m = n$. Las $c$‘s compensan el exceso de $a$‘s sobre $b$‘s.
2. $n < m$: entonces $k = m - n$, es decir, $k + n = m$. Las $c$‘s compensan el exceso de $b$‘s sobre $a$‘s.

Idea del PDA

Usamos un NPDA que de forma no determinista elige entre los dos casos:

• Caso $n \geq m$: Apilamos una marca por cada $a$. Luego, por cada $b$, desapilamos una marca. Si sobran marcas en la pila despues de las $b$‘s, las desapilamos con las $c$‘s.
• Caso $n < m$: Apilamos una marca por cada $a$. Luego, por cada $b$, primero desapilamos las marcas de las $a$‘s, y cuando se acaban, apilamos marcas por las $b$‘s sobrantes. Las $c$‘s desapilan estas marcas.

Definicion formal

$M = (\{q_0, q_1, q_2, q_3, q_4, q_f\}, \{a, b, c\}, \{X, Z_0\}, \delta, q_0, Z_0, \{q_f\})$

El automata acepta por estado final.

Transiciones

Estado $q_0$ (leyendo $a$‘s):

$$\begin{aligned} \delta(q_0, a, Z_0) &= \{(q_0, XZ_0)\} \\ \delta(q_0, a, X) &= \{(q_0, XX)\} \\ \end{aligned}$$

Transicion no determinista al empezar a leer $b$‘s:

$$\begin{aligned} \delta(q_0, b, X) &= \{(q_1, \varepsilon)\} &\quad \text{(caso } n \geq m\text{)} \\ \delta(q_0, b, X) &\ni (q_3, \varepsilon) &\quad \text{(caso } n < m\text{, mismo origen)} \\ \delta(q_0, b, Z_0) &= \{(q_3, XZ_0)\} &\quad \text{(caso } n = 0\text{)} \\ \delta(q_0, \varepsilon, Z_0) &= \{(q_f, \varepsilon)\} &\quad \text{(caso } n = m = k = 0\text{)} \\ \delta(q_0, \varepsilon, X) &= \{(q_2, X)\} &\quad \text{(caso } m = 0\text{, saltar a leer } c\text{'s)} \\ \end{aligned}$$

Estado $q_1$ (caso $n \geq m$, desapilando $a$‘s con $b$‘s):

$$\begin{aligned} \delta(q_1, b, X) &= \{(q_1, \varepsilon)\} \\ \delta(q_1, \varepsilon, X) &= \{(q_2, X)\} &\quad \text{(quedan } a\text{'s, pasar a leer } c\text{'s)} \\ \delta(q_1, \varepsilon, Z_0) &= \{(q_f, \varepsilon)\} &\quad \text{(} n = m, k = 0 \text{)} \\ \end{aligned}$$

Estado $q_2$ (leyendo $c$‘s, desapilando exceso):

$$\begin{aligned} \delta(q_2, c, X) &= \{(q_2, \varepsilon)\} \\ \delta(q_2, \varepsilon, Z_0) &= \{(q_f, \varepsilon)\} \\ \end{aligned}$$

Estado $q_3$ (caso $n < m$, $b$‘s exceden las $a$‘s apiladas):

$$\begin{aligned} \delta(q_3, b, X) &= \{(q_3, \varepsilon)\} &\quad \text{(aun desapilando } a\text{'s)} \\ \delta(q_3, b, Z_0) &= \{(q_4, XZ_0)\} &\quad \text{(} a\text{'s agotadas, apilar exceso de } b\text{'s)} \\ \end{aligned}$$

Estado $q_4$ (apilando exceso de $b$‘s):

$$\begin{aligned} \delta(q_4, b, X) &= \{(q_4, XX)\} \\ \delta(q_4, \varepsilon, X) &= \{(q_2, X)\} &\quad \text{(pasar a leer } c\text{'s)} \\ \end{aligned}$$

Ejemplos de aceptacion

| Cadena | $n$ | $m$ | $k = |n-m|$ | Caso | |--------|-----|-----|------|------| | $\varepsilon$ | 0 | 0 | 0 | $n = m$ | | $aabcc$ | 2 | 1 | 1 | $n > m$ | | $abbb\,cc$ | 1 | 3 | 2 | $n < m$ | | $ab$ | 1 | 1 | 0 | $n = m$ | | $aacc$ | 2 | 0 | 2 | $n > m$ | | $bbcc$ | 0 | 2 | 2 | $n < m$ |

Verificacion interactiva

Traza para $aabc$ (caso $n > m$, $k = 1$):

Traza para $ab$ (caso $n = m$, $k = 0$):

Verificacion de $aabc$

1. $(q_0, aabc, Z_0) \vdash (q_0, abc, XZ_0)$ — leer $a$, apilar $X$
2. $(q_0, abc, XZ_0) \vdash (q_0, bc, XXZ_0)$ — leer $a$, apilar $X$
3. $(q_0, bc, XXZ_0) \vdash (q_1, c, XZ_0)$ — leer $b$, desapilar $X$ (caso $n \geq m$)
4. $(q_1, c, XZ_0) \vdash (q_2, c, XZ_0)$ — $\varepsilon$-transicion a $q_2$
5. $(q_2, c, XZ_0) \vdash (q_2, \varepsilon, Z_0)$ — leer $c$, desapilar $X$
6. $(q_2, \varepsilon, Z_0) \vdash (q_f, \varepsilon, \varepsilon)$ — acepta $\checkmark$