Verdadero o falso: un PDA no puede aceptar el lenguaje {epsilon}

La intuicion: epsilon es la cadena mas facil de aceptar

La afirmacion dice que un PDA no puede aceptar $\{\varepsilon\}$. Esto es falso. De hecho, $\varepsilon$ es probablemente la cadena mas facil de aceptar para cualquier tipo de automata.

Si el PDA acepta por estado final, basta con que el estado inicial sea tambien de aceptacion y no definir ninguna transicion. Al arrancar, el automata ya esta en un estado final, asi que acepta $\varepsilon$ inmediatamente. Cualquier otra cadena no se puede procesar porque no hay transiciones.

Si el PDA acepta por pila vacia, definimos una sola transicion: al estar en el estado inicial leyendo $\varepsilon$ con $Z_0$ en el tope, desapilamos $Z_0$. La pila queda vacia sin haber leido nada, asi que acepta $\varepsilon$. Cualquier otra cadena no se puede consumir porque la pila ya esta vacia antes de empezar a leer. En ambos casos, el PDA acepta exactamente $\{\varepsilon\}$.

Respuesta

FALSO. Contraejemplo:

Contraejemplo 1 — Aceptacion por pila vacia

$M = (\{q_0\}, \{a,b\}, \{Z_0\}, \delta, q_0, Z_0)$

$\delta(q_0, \varepsilon, Z_0) = \{(q_0, \varepsilon)\}$

$L(M) = \{\varepsilon\}$

Contraejemplo 2 — Aceptacion por estado final

$M' = (\{q_0\}, \{a,b\}, \{Z_0\}, \delta', q_0, Z_0, \{q_0\})$

$\delta' = \emptyset$

$L(M') = \{\varepsilon\} \quad \square$

Automata

Solucion

La afirmacion es FALSA.

Un automata de pila si puede aceptar el lenguaje $\{\varepsilon\}$ (el lenguaje que contiene unicamente la cadena vacia).

Contraejemplo: PDA que acepta por estado final

Definimos el PDA $M' = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ con:

$$\begin{aligned} Q &= \{q_0\} \\ F &= \{q_0\} \\ \end{aligned}$$

y $\delta$ sin ninguna transicion definida. Como $q_0$ es tanto estado inicial como estado de aceptacion, el PDA acepta $\varepsilon$ inmediatamente (ya esta en un estado final al empezar). Cualquier otra cadena no vacia sera rechazada porque no hay transiciones para procesar simbolos.

Contraejemplo: PDA que acepta por pila vacia

Definimos el PDA $M = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ donde:

$$\begin{aligned} Q &= \{q_0\} \\ \Sigma &= \{a, b\} \quad \text{(cualquier alfabeto)} \\ \Gamma &= \{Z_0\} \\ q_0 &= q_0 \\ Z_0 &= Z_0 \\ \end{aligned}$$

Con la unica transicion:

$\delta(q_0, \varepsilon, Z_0) = \{(q_0, \varepsilon)\}$

Este PDA, al recibir la cadena vacia $\varepsilon$, inmediatamente desapila $Z_0$ (reemplazandolo por $\varepsilon$), dejando la pila vacia. Por lo tanto, acepta $\varepsilon$ por pila vacia.

Para cualquier otra cadena $w \neq \varepsilon$, la unica transicion disponible vacia la pila antes de leer cualquier simbolo de entrada, y como no hay mas transiciones posibles, el PDA se queda atascado sin consumir la entrada. No acepta.

Conclusion

En ambos modelos de aceptacion (pila vacia o estado final), es posible construir un PDA que acepte exactamente el lenguaje $\{\varepsilon\}$.