Equivalencia entre AFPNDs aceptando con pila vacía y aceptando en estado final

Para cada AFPND $M$ que acepta con pila vacía existe un AFPND $M^\prime$ que acepta en estado final.

Idea de la comprobación:

• $M^\prime$ simula $M$
• $M^\prime$ usa un nuevo símbolo $c_0^\prime$ como símbolo inicial de la pila
• si después de la simulación de $M$ dicho $c_0^\prime$ está en la cima de la pila, $M^\prime$ sabe que $M$ hubiese aceptado, es decir, $M^\prime$ acepta también yiendo a un estado final.

Para el ejemplo de antes

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

con el siguiente autómata que acepta con pila vacía

obtenemos el nuevo autómata que acepta en estado final

En general:

$$\begin{eqnarray*} M&=&(\Sigma,\Gamma,Q,\delta,q_0,c_0,\emptyset)\\ M^\prime&=... ...Q\cup\{q_0^\prime,f\},\delta^\prime,q_0^\prime,c_0^\prime,\{f\}) \end{eqnarray*}$$

con

• $q_0^\prime,f\notin Q$, es decir, son nuevos estados
• $c_0^\prime\notin \Gamma$, es decir, es un nuevo símbolo inicial
• $\delta^\prime(q_0^\prime,\epsilon,c_0^\prime)=\{(q_0,c_0c_0^\prime)\}$, es decir, la primera transición apila el antiguo símbolo inicial y se va al antiguo estado inicial sin leer nada de la entrada
• $\forall q\in Q,\sigma\in\Sigma,\gamma\in\Gamma: \delta^\prime(q,\sigma,\gamma)=... ...ta(q,\sigma,\gamma), \delta^\prime(q,\epsilon,\gamma)=\delta(q,\epsilon,\gamma)$, es decir, se simula $M$
• $\forall q\in Q: \delta^\prime(q,\epsilon,c_0^\prime)=\{(f,c_0^\prime)\}$, es decir, si la pila solamente contiene el nuevo símbolo inicial se va al estado final.

Para cada AFPND $M$ que acepta en estado final existe un AFPND $M^\prime$ que acepta con pila vacía.

Idea de la comprobación:

• $M^\prime$ simula $M$
• $M^\prime$ vacía desde cualquier estado final de $M$ su pila
• tenemos que tener cuidado si $M$ no termina en estado final, pero su pila está vacía: colocamos antes de la simulación un nuevo símbolo $c_0^\prime$ como símbolo inicial en la pila que no `se toca' durante la simulación de $M$.

Para el ejemplo

$$L=\{a^ib^j\;\vert\;j\leq i \}$$

con el siguiente autómata que acepta en estado final

(Primero observamos la consecuencia de la definición de un cálculo:

$$M\mbox{ acepta } w \Longleftrightarrow (q_0,w,c_0)\shortmid\joinrel\relbar\joinrel\relbar ^*(f,\epsilon,v)$$

entonces, si sobran $b$'s la pila estará vacía y no habrá transición ninguna, y por eso no llegamos a $\epsilon$ con la entrada.)

Siguiendo la idea, obtenemos el nuevo autómata que acepta con pila vacía

En general:

$$\begin{eqnarray*} M&=&(\Sigma,\Gamma,Q,\delta,q_0,c_0,\emptyset)\\ M^\prime&=... ...\prime,q^\prime\},\delta^\prime,q_0^\prime,c_0^\prime,\emptyset) \end{eqnarray*}$$

con

• $q_0^\prime,q^\prime\notin Q$, es decir, son nuevos estados
• $c_0^\prime\notin \Gamma$, es decir, es un nuevo símbolo inicial
• $\delta^\prime(q_0^\prime,\epsilon,c_0^\prime)=\{(q_0,c_0c_0^\prime)\}$, es decir, la primera transición apila el antiguo símbolo inicial y se va al antiguo estado inicial sin leer nada de la entrada
• $\forall\gamma\in\Gamma\cup\{c_0^\prime\}: \delta^\prime(q^\prime,\epsilon,\gamma)=\{(q^\prime,\epsilon)\}$, es decir, una vez en estado $q^\prime$ se vacía la pila sin modificar la entrada
• $\forall q\in Q,\sigma\in\Sigma,\gamma\in\Gamma: \delta^\prime(q,\sigma,\gamma)=\delta(q,\sigma,\gamma)$, es decir, pasos normales de la simulación
• $\forall q\in Q-F,\gamma\in\Gamma: \delta^\prime(q,\epsilon,\gamma)=\delta(q,\epsilon,\gamma)$, es decir, se simula también las transiciones $\epsilon$ mientras $M$ no esté en estado final
• $\forall q\in F,\gamma\in\Gamma: \delta^\prime(q,\epsilon,\gamma)=\delta(q,\epsilon,\gamma) \cup\{(q^\prime,\gamma)\}$, es decir, saltamos al estado que vacía la pila si ya estamos en estado final