Siguiente: Autómatas de pila deterministas Un nivel arriba: Autómatas de pila Anterior: Reconocimiento de lenguajes

Autómatas de pila y lenguajes libres de contexto

Se tiene que una condición para que un lenguaje sea reconocido por un autómata de pila es que ese lenguaje sea libre de contexto. En esta sección probaremos y ejemplificaremos que la condición es necesaria. Pospondremos la suficiencia de esta condición a la exposición de los lenguajes libres de contexto.

Proposición 3.1   Para cualquier autómata de pila $\mbox{\it AutP\/}=(Q,\mbox{\it Ent\/},\mbox{\it AlfP\/},\mbox{\it tran\/},q_0,X,\emptyset)$ su lenguaje $L=\mbox{\it LPV\/}(\mbox{\it AutP\/})$ es libre de contexto.

En efecto, sea $G=(V,\mbox{\it Ent\/},P,S)$ la gramática tal que

$$\begin{eqnarray*}V &=& (Q\times \mbox{\it AlfP\/}\times Q)\cup\{S\}, \\ S &:& ... ...s por las transiciones de $\mbox{\it AutP\/}$ : \end{minipage}} \end{eqnarray*}$$

1.

$\forall q\in Q:\ S\rightarrow [q_0,X,q]$

2.

$\forall q\in Q,e\in\mbox{\it Ent\/},Y\in\mbox{\it AlfP\/}:$ si $(q',Y_1Y_2\cdots Y_m)\in\mbox{\it tran\/}(q,e,Y)$ entonces inclúyase la producción

$$[q,Y,q^{(m+1)}]\rightarrow e[q',Y_1,q^{(2)}][q^{(2)},Y_2,q^{(3)}]\cdots[q^{(m)},Y_m,q^{(m+1)}]$$

para cualesquiera selecciones de los estados $q^{(2)},\ldots,q^{(m)},q^{(m+1)},\in Q$.

3.

$\forall q\in Q,e\in\mbox{\it Ent\/},Y\in\mbox{\it AlfP\/}:$ si $(q',Y_1Y_2\cdots Y_m)\in\mbox{\it tran\/}(q,\mbox{\it nil\/},Y)$ entonces inclúyase la producción

$$[q,Y,q^{(m+1)}]\rightarrow [q',Y_1,q^{(2)}][q^{(2)},Y_2,q^{(3)}]\cdots[q^{(m)},Y_m,q^{(m+1)}]$$

para cualesquiera selecciones de los estados $q^{(2)},\ldots,q^{(m)},q^{(m+1)},q^{(m+2)}\in Q$.

4.

$\forall q\in Q,e\in\mbox{\it Ent\/},Y\in\mbox{\it AlfP\/}:$ si $(q',\mbox{\it nil\/})\in\mbox{\it tran\/}(q,e,Y)$ entonces inclúyase la producción $[q,Y,q']\rightarrow e$.

5.

$\forall q\in Q,e\in\mbox{\it Ent\/},Y\in\mbox{\it AlfP\/}:$ si $(q',\mbox{\it nil\/})\in\mbox{\it tran\/}(q,\mbox{\it nil\/},Y)$ entonces inclúyase la producción $[q,Y,q']\rightarrow \mbox{\it nil\/}$.

La idea subyacente en esta construcción consiste en que toda derivación siniestra en la gramática definida ha de simular una computación reconocedora en el autómata dado. Veamos que para cualquier palabra $\sigma \in \mbox{\it Ent\/}^*$ y para cualesquiera $q,q'\in Q$, $Y\in\mbox{\it AlfP\/}$ se cumple

$$G\vdash \left([q,Y,q']\stackrel{*}{\Rightarrow}\sigma\right)\... ...\sigma;Y\stackrel{*}{\Rightarrow}q'\mbox{\it nil\/};X\right)$$ (51)

$\Leftarrow )$ Mostremos esta implicación por inducción en el número de pasos de derivación. Caso base: Supongamos que la DI $q'\mbox{\it nil\/};X$ se siga inmediatamente de la DI $q\sigma;Y$. Entonces $\sigma$ consta a lo sumo de un símbolo y necesariamente $(q',\mbox{\it nil\/})\in\mbox{\it tran\/}(q,\sigma,Y)$. Por tanto, $[q,Y,q']\rightarrow\sigma$ es una producción legal en G. Eso da el correspondiente miembro izquierdo de la relación 5.1. Caso inductivo: Sea k>0. Supongamos que si $q'\mbox{\it nil\/};X$ se deriva de $q\sigma;Y$ en a lo sumo k pasos, entonces $G\vdash \left([q,Y,q']\stackrel{*}{\Rightarrow}\sigma\right)$. Consideremos ahora el caso en el que $q'\mbox{\it nil\/};X$ se deriva de $q\sigma;Y$ en exactamente k+1 pasos. Escribamos $\sigma=s_1\sigma_1$. Necesariamente, existe una primera DI $q^{(1)}\sigma_1;Y_1\cdots Y_m$ tal que

$$\mbox{\it AutP\/}\vdash q\sigma;Y\Rightarrow \left(q^{(1)}\si... ...\cdots Y_m \right)\stackrel{*}{\Rightarrow}q'\mbox{\it nil\/};X$$

donde la última derivación se hace en a lo sumo k pasos. Descompongamos $\sigma_1$ en m tramos, $\sigma_1=\sigma_1^{(1)}\cdots\sigma_1^{(m)}$, donde cada $\sigma_1^{(i)}$ realiza el efecto global de ``desempilar'' al símbolo Y_i. Se tiene que existen $q^{(2)},q^{(3)},\ldots,q^{(m)},q^{(m+1)}=q'\in Q$ tales que

$$\forall i\leq m:\ \mbox{\it AutP\/}\vdash \left(q^{(i)}\sigma... ...\stackrel{*}{\Rightarrow}q^{(i+1)}\mbox{\it nil\/};X\right).$$ (52)

Por la hipótesis de inducción se tiene $G\vdash \left([q^{(i)},Y_i,q^{(i+1)}]\stackrel{*}{\Rightarrow}\sigma_1^{(i)}\right).$ Ahora, de la primera derivación $\mbox{\it AutP\/}\vdash q\sigma;Y\Rightarrow q^{(1)}\sigma_1;Y_1\cdots Y_m$, se tiene

$$G\vdash \left([q,Y,q']\rightarrow s_1[q^{(1)},Y_1,q^{(2)}][q^{(2)},Y_2,q^{(3)}]\cdots[q^{(m)},Y_m,q^{(m+1)}]\right),$$ (53)

y consecuentemente, de 5.2 y 5.3 $G\vdash \left([q,Y,q']\stackrel{*}{\Rightarrow}\sigma\right)$. $\Rightarrow)$ Mostremos ahora la implicación recíproca por inducción en el número de pasos de derivación. Caso base: Si $[q,Y,q']\rightarrow\sigma$ es una producción legal en G, entonces $\sigma$ consta a lo sumo de un símbolo y $(q',\mbox{\it nil\/})\in\mbox{\it tran\/}(q,\sigma,Y)$. Por tanto la DI $q'\mbox{\it nil\/};X$ se sigue inmediatamente de la DI $q\sigma;Y$. Esto da el correspondiente miembro derecho de la relación 5.1. Caso inductivo: Sea k>0. Supongamos que si $G\vdash \left([q,Y,q']\stackrel{*}{\Rightarrow}\sigma\right)$ se deriva en a lo sumo k pasos, entonces $q'\mbox{\it nil\/};X$ se deriva de $q\sigma;Y$. Consideremos ahora el caso en el que $\sigma$ se deriva de [q,Y,q'] en exactamente k+1 pasos. Escribamos $\sigma=s_1\sigma_1$. Necesariamente, para una primera derivación se ha de tener

$$[q,Y,q']\rightarrow \left(s_1[q^{(1)},Y_1,q^{(2)}][q^{(2)},Y_... ...s[q^{(m)},Y_m,q^{(m+1)}]\right) \stackrel{*}{\Rightarrow}\sigma$$

donde la última derivación se hace en a lo sumo k pasos. Escribamos $\sigma_1=\sigma_1^{(1)}\cdots\sigma_1^{(m)}$, donde cada $\sigma_1^{(i)}$ es tal que $G\vdash [q^{(i)},Y_1,q^{(i+1)}] \stackrel{*}{\Rightarrow} \sigma_1^{(i)}$. Por la hipótesis de inducción se tiene que $\forall i\leq m:\ \mbox{\it AutP\/}\vdash \left(q^{(i)}\sigma_1^{(i)};Y_i\stackrel{*}{\Rightarrow}q^{(i+1)}\mbox{\it nil\/};X\right)$ y de aquí se tiene también que

$$\forall i\leq m:\ \mbox{\it AutP\/}\vdash \left(q^{(i)}\sigma... ...htarrow}q^{(i+1)}\mbox{\it nil\/};Y_{i+1}\cdots Y_mX\right).$$ (54)

Como $[q,Y,q']\rightarrow \left(s_1[q^{(1)},Y_1,q^{(2)}][q^{(2)},Y_2,q^{(3)}]\cdots[q^{(m)},Y_m,q^{(m+1)}]\right)$ es una producción, necesariamente

$$q\sigma;X\rightarrow q^{(1)}\sigma_1^{(1)};Y_{1}Y_{2}\cdots Y_mX$$ (55)

y consecuentemente, de 5.4 y 5.5 $\mbox{\it AutP\/}\vdash \left(q\sigma;X\stackrel{*}{\Rightarrow}q'\mbox{\it nil\/};X\right)$. q.e.d. Ejemplo: En un ejemplo anterior, vimos que el lenguaje $L=\{0^{3n}1^n\vert n\geq 0\}$ es reconocido por el autómata

$$\begin{array}{\vert\vert c\vert c\vert\vert}\hline\hline \be... ...t\{ (q_1,A) \right\} \end{array} \\ \hline\hline \end{array}$$

donde en cualquier otra configuración, la función de transición asocia el conjunto vacío. De acuerdo con la construcción anterior, el conjunto de variables de la gramática que simula computaciones en el autómata es $V=(Q\times \mbox{\it AlfP\/}\times Q)\cup\{S\}$ el cual, en este caso, tiene $4\cdot 3\cdot 4+1=49$ símbolos. Construyendo las producciones conforme van apareciendo los símbolos variables, obtenemos lo siguiente: Producciones para S: Las producciones ``iniciales'' son $S \rightarrow {[q_0,X,q_k]}$ con k=0,1,2,3. Producciones para [q₀,X,q_k]: Como $(q_0,0,X) = \left\{ (q_0,CX) \right\}$, tenemos las producciones

$${[q_0,X,q_k]} \rightarrow 0{[q_0,C,q_j]}{[q_j,X,q_k]} \hspace{3em} j,k=0,1,2,3.$$

Producciones para [q₀,C,q_k]: Como $(q_0,0,C) = \left\{ (q_0,CC),(q_1,CC) \right\}$ y $(q_0,1,C) = \left\{ (q_2,\mbox{\it nil\/}) \right\}$, tenemos las producciones

$$\begin{eqnarray*}{[q_0,C,q_k]} &\rightarrow & 0{[q_0,C,q_j]}{[q_j,C,q_k]} \hspac... ...} \hspace{3em} j,k=0,1,2,3 \\ {[q_0,C,q_2]} &\rightarrow & 1 \end{eqnarray*}$$

Producciones para [q₁,C,q₂]: Como $(q_1,1,C) = \left\{ (q_2,\mbox{\it nil\/}) \right\}$, tenemos la producción ${[q_1,C,q_2]} \rightarrow 1$. Producciones para [q₂,C,q₃] y [q₃,C,q₁]: Como $(q_2,\mbox{\it nil\/},C) = \left\{ (q_3,\mbox{\it nil\/}) \right\}$ y $(q_3,\mbox{\it nil\/},C) = \left\{ (q_1,\mbox{\it nil\/}) \right\}$, tenemos las producciones ${[q_2,C,q_3]} \rightarrow \mbox{\it nil\/}$ y ${[q_3,C,q_1]} \rightarrow \mbox{\it nil\/}$. Producciones para [q₁,X,q₁]: Como $(q_1,\mbox{\it nil\/},X) = \left\{ (q_1,\mbox{\it nil\/}) \right\}$, tenemos la producción ${[q_1,X,q_1]} \rightarrow \mbox{\it nil\/}$. Producciones de errores: Como $(q_0,1,X) = \left\{ (q_1,A) \right\}$, tenemos la producción

$${[q_0,X,q_k]} \rightarrow 1{[q_1,A,q_k]}.$$

De manera similar, de las demás condiciones de error tendremos las producciones

$$\begin{array}{lcr} {[q_1,X,q_k]} &\rightarrow & 1{[q_1,A,q_k... ...} \\ {[q_3,X,q_k]} &\rightarrow & {[q_1,A,q_k]} \end{array}$$

y no hay producciones para variables de la forma [q_i,A,q_k], por lo que una vez que se generaron no hay manera de conducirlas a una palabra terminal. Reescribamos las variables como se indica a continuación:

$$\begin{array}{\vert\vert c\vert\vert c\vert\vert c\vert\vert}... ..._3 &:& {[q_3,C,q_3]} \end{array} \\ \hline\hline \end{array}$$

En la codificación anterior entre las variables de la forma [q_j,X,q_k] sólo consideramos a F=[q₁,X,q₁] pues las demás no aparecen como antecedentes de ninguna producción. Entonces, las producciones que no corresponden a situaciones de error son las siguientes:

$$\begin{array}{\vert\vert c\vert\vert c\vert\vert c\vert\vert}... ...C_2D_3 \vert 0C_3E_3 \end{array} \\ \hline\hline \end{array}$$

Ahora, si suprimimos a las producciones que en su consecuente tengan símbolos que no aparecen en el antecedente de ninguna otra producción (pues esos símbolos no podrán sustituirse y por tanto no derivan ninguna palabra terminal) se tiene las producciones:

$$\begin{array}{\vert\vert c\vert\vert c\vert\vert c\vert\vert}... ...B_2D_3 \vert 0C_2D_3 \end{array} \\ \hline\hline \end{array}$$

Observemos ahora que toda vez que se genera B₀ no hay manera de suprimirla. Por tanto, ninguna derivación terminal puede involucrar a esa variable. Así pues, omitiendo las producciones que involucran a B₀ se tiene la gramática

$$\begin{array}{\vert\vert c\vert\vert c\vert\vert}\hline\hline... ...B_2D_3 \vert 0C_2D_3 \end{array} \\ \hline\hline \end{array}$$

la cual efectivamente genera al lenguaje L.
Siguiente: Autómatas de pila deterministas Un nivel arriba: Autómatas de pila Anterior: Reconocimiento de lenguajes