Autómatas finitos con pila deterministas (AFPD)

Los AFPND, como el propio nombre ya dice, no son deterministas, es decir, pueden existir varias posibles configuraciones siguientes, o en otras palabras, $\delta(q,\sigma,\gamma)$ o $\delta(q,\epsilon,\gamma)$ son conjuntos con--posiblemente--más de un elemento.

Para que un AFPND acepte una palabra de entrada $w$ se ha exigido solamente la existencia de un cálculo que lee toda la palabra $w$ y termina con pila vacía o en un estado final.

Este hecho no es adecuado en la práctica, porque de alguna manera hay que comprobar todos los posibles cálculos para ver si existe uno que acepta. Por eso limitamos los autómatas para que sean deterministas.

Podemos definir un autómata finito con pila determinista AFPD

$$M=(\Sigma,\Gamma,Q,\delta,q_0,c_0,F)$$

igual que un AFPND introduciendo las siguientes restricciones

1. para cada $q\in Q$, $\sigma\in\Sigma$, y $\gamma\in\Gamma$ permitimos como mucho una transición, es decir:
   
   $$\vert\delta(q,\sigma,\gamma)\vert+\vert\delta(q,\epsilon,\gamma)\vert\le 1$$
   
   
   Entonces, permitimos transiciones-$\epsilon$ que son deterministas si consideramos la pila.
2. $F\not=\emptyset$, es decir, el AFND acepta con estado final.

Dado que para un AFPD existe como mucho una configuración siguiente, es decir $\shortmid\joinrel\relbar\joinrel\relbar$ es una función, los cálculos se convierten en cadenas deterministas, y decimos, que el AFPD acepta una palabra $w$ si existe el cálculo $(q_0,w,c_0)\shortmid\joinrel\relbar\joinrel\relbar (f,\epsilon,v)$ con $f\in F$.

Para AFPDs los dos criterios de parada no son equivalentes que se entiende analizando las comprobaciones donde era escencial disponer de transiciones no-deterministas para `saltar' a un estado adicional con el fin de vaciar la pila.

Llamamos un lenguaje $L$ libre de contexto determinista si $L$ es aceptado por un autómata finito con pila determinista.

Los lenguajes libres de contexto deterministas son un verdadero subconjunto de los lenguajes libres de contexto, es decir, existen lenguajes que son libres de contexto pero no libres de contexto determinista.

Ejemplo:

El lenguaje $L=\{w\;\vert\;w\in\{0,1,\char93 \}, w=v\char93 v^R \mbox{ y $v$ no contiene $\char93 $ }$ es libre de contexto determinista, porque se apila hasta encontrar el centro (que hemos marcado con $\char93$) y después se verifica el resto de $w$ con el contenido de la pila.

El lenguaje $L=\{w\;\vert\;w\in\{0,1\}, w=vv^R\}$ es libre de contexto, como ya vimos, pero no es libre de contexto determinista, porque, para decirlo de alguna manera, se necesita el no-determinismo para encontrar el centro, o en otras palabras, hay que comprobar todos los posibles cálculos verificando si uno de ellos llega a una aceptación.

Obviamente los lenguajes regulares también son libres de contexto deterministas, porque si ``no usamos la pila'' justamente un AFP es un AFD.