Autómatas finitos con pila no-deterministas (AFPND)

Un autómata finito con pila no-determinista (AFPND) es una séptupla

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

donde

• $\Sigma$ es un alfabeto de entrada.
• $\Gamma$ es un alfabeto de pila ($\Gamma=\Sigma$ es posible).
• $Q$ es un conjunto de estados, $\vert Q\vert<\infty$.
• $q_0\in Q$ es el estado inicial.
• $c_0\in\Gamma$ es el símbolo inicial de la pila.
• $F$ es el conjunto de estados finales (puede ser el conjunto vacía).
• $\delta$ es la función de transición
  
  $$\delta:Q\times(\Sigma\cup\{\epsilon\}\times\Gamma\longrightarrow W_{<\infty}(Q\times\Gamma^*)$$
  
  
  donde $W_{<\infty}$ sea el conjunto de subconjuntos finitos.

  Es decir, el comportamiento del autómata depende en cada transición

  • del estado actual
  • posiblemente del siguiente símbolo de la entrada
  • del símbolo en la cima de la pila
  y se modifica el autómata en el sentido que
  • se cambia (posiblemente) del estado
  • se consume (posiblemente) el siguiente símbolo de la entrada
  • se modifica (posiblemente) el contenido de la cima de la pila.

Para el ejemplo de arriba obtenemos el autómata

$$M_{()}=( \{(,),\langle,\rangle,[,]\}, \{(,\langle,[,\char93 \}, \{q_0,q_1\},\delta,q_0,\char93 ,\emptyset)$$

con

$$\begin{eqnarray*} \delta(q_0,(,\gamma) &=& \{(q_0,(\gamma)\}\quad\forall\gamma\i... ...)\} \\ \delta(q_0,\epsilon,\char93 ) &=& \{(q_1,\epsilon)\} \\ \end{eqnarray*}$$

Observa

• que escribimos en las expresiones arriba el contenido de la pila como los árabes: desde la derecha hacia la izquierda,
• que el autómata no está completo, pero se podría completar añadiendo transiciones adecuados en un estado ``sin salida'' que ya no varía la pila.

También podemos dibujar autómatas con pila, por ejemplo de la siguiente manera:

Es decir, dibujamos el grafo parecido como lo hemos hecho para los AFND-$\epsilon$: los vértices del grafo representan los estados del autómata y las aristas representan las transiciones. Ampliamos las etiquetas de las aristas con los cambios en la cima de la pila.

Podemos pensar de un autómata con pila como un dispositivo que lee desde una cinta con símbolos, realiza cambios de estados internamente, y maneja una pila de la forma descrita:

Otro ejemplo; construimos un AFP para el lenguaje

$$L_{vv^R}=\{w\;\vert\;w\in\{0,1\}^*, w=vv^R\}$$

es decir, los palíndromos con longitud par.

Idea:

• Adivinamos (no-determinismo) dónde acaba $v$.
• Copiamos toda la palabra $v$ a la pila.
• Verificamos el resto de $w$, que debe ser $v^R$, con el contenido de la pila, es decir, la pila debe estar vacía una vez haber leído toda la palabra $w$.

Un AFPND será el siguiente:

$$M_{vv^R}=( \{0,1\}, \{0,1,\char93 \}, \{q_0,q_1,q_2\},\delta,q_0,\char93 ,\emptyset)$$

con

$$\begin{eqnarray*} \delta(q_0,0,\gamma) &=& \{(q_0,0\gamma)\}\quad\forall\gamma\i... ...)\} \\ \delta(q_1,\epsilon,\char93 ) &=& \{(q_2,\epsilon)\} \\ \end{eqnarray*}$$

¿Cómo comprobamos que es correcto?

Dado que el contenido de la pila influye en el comportamiento del autómata necesitamos una notación para describir los cálculos del autómata.

La configuración (o descripción instantánea) $C$ de un AFP $M=(\Sigma,\Gamma,Q,\delta,q_0,c_0,F)$ es la tripla $(q,u,v)$ donde

• $q\in Q$ es el estado actual
• $u\in\Sigma^*$ es lo que queda por leer de la entrada
• $v\in\Gamma^*$ es el contenido actual de la pila

La configuración inicial $C_0$ entonces es $(q_0,w,c_0)$.

Si el autómata está en configuración $C$ podemos definir que es una posible siguiente configuración, es decir, después de haber realizado un paso en el cálculo.

$C^\prime=(q^\prime,u,zv)$ es configuración sucesora de $C=(q,\sigma u,\gamma v)$ (es decir, $\sigma$ es el siguiente símbolo de la entrada y $\gamma$ la cima de la pila), si $(q^\prime,z)\in\delta(q,\sigma,\gamma)$ y, para las transiciones $\epsilon$, $C^\prime=(q^\prime,u,zv)$ es configuración sucesora de $C=(q,u,\gamma v)$ (es decir, no se lee un símbolo de la entrada y $\gamma$ la cima de la pila), si $(q^\prime,z)\in\delta(q,\epsilon,\gamma)$.

Observa, si la pila está vacía, no existe configuración sucesora ninguna.

Escribimos $C\shortmid\joinrel\relbar\joinrel\relbar C^\prime$ si $C^\prime$ es configuración sucesora de $C$. Si existe una secuencia de configuraciones sucesoras de $C$ hasta $C^\prime$, es decir,

$$C=C_0\shortmid\joinrel\relbar\joinrel\relbar C_1\shortmid\joi... ...lbar \dots\shortmid\joinrel\relbar\joinrel\relbar C_n=C^\prime$$

llamamos la secuencia un cálculo del autómata y abreviamos con $C\shortmid\joinrel\relbar\joinrel\relbar ^*C^\prime$.

Un AFPND acepta una palabra $w$ de entrada según modus:

• $F=\emptyset$, es decir, acepta con pila vacía
  
  $$M\mbox{ acepta } w \Longleftrightarrow (q_0,w,c_0)\shortmid\joinrel\relbar\joinrel\relbar ^*(q,\epsilon,\epsilon)$$
  
  
  para cualquier estado $q\in Q$
• $F\not=\emptyset$, es decir, acepta en estado final
  
  $$M\mbox{ acepta } w \Longleftrightarrow (q_0,w,c_0)\shortmid\joinrel\relbar\joinrel\relbar ^*(f,\epsilon,v)$$
  
  
  con $v\in\Gamma^*$ y $f\in F$.

El lenguaje aceptado por un autómata AFPND $M$ es

$$L(M) = \{ w \;\vert\;M \mbox{ acepta } w \}$$

En la siguiente sección comprobamos que ambos métodos de aceptación son equivalentes para los AFPND (pero no será el caso de ls AFPD, los autómatas finitos con pila deterministas, que veremos más adelante).

Comprobamos ahora que el $M_{vv^R}$ es correcto, es decir, tenemos que comprobar que $L(M_{vv^R})=L_{vv^R}$.

Primero verificamos que $M_{vv^R}$ acepta para cualquier palabra $v\in\{0,1\}^*$ la palabra $w=vv^R$:

$$\begin{eqnarray*} (q_0,vv^R,\char93 ) &\longrightarrow ^*&(q_0,v^R,v^R\char93 )\... ...psilon,\char93 )\\ &\longrightarrow &(q_2,\epsilon,\epsilon)\\ \end{eqnarray*}$$

es decir, hemos encontrado un cálculo y con eso sabemos que $L_{vv^R}\subset L(M_{vv^R})$.

Luego comprobamos que $M_{vv^R}$ solamente acepta palabras en $L_{vv^R}$.

(por incluir)