Siguiente: Autómatas de pila con Un nivel arriba: Autómatas de pila Anterior: Autómatas de pila y

Autómatas de pila deterministas

Un autómata de pila determinista es un autómata de pila

$$\mbox{\it AutP\/}=(Q,\mbox{\it Ent\/},\mbox{\it AlfP\/},\mbox{\it tran\/},q_0,X,F)$$

donde se cumplen las siguientes dos propiedades:

• Para cualquier pareja (estado,tope_de_la_pila) se tiene que o bien el autómata tiene definida la transición correspondiente a la palabra de entrada vacía o bien la tiene definida en símbolos del alfabeto de entrada, y
• para cualquier terceta (estado,s,tope_de_la_pila), la transición correspondiente contiene, a lo sumo, una pareja (nuevo_estado,tope_de_la_pila).

En símbolos,

$$\begin{array}{lrcl} \forall (q,Y)\in Q\times \mbox{\it AlfP\... ...ox{\it tran\/}(q,\mbox{\it nil\/},Y)\right)\leq 1 \end{array}$$

Sea $\mbox{\it AutP\/}=(Q,\mbox{\it Ent\/},\mbox{\it AlfP\/},\mbox{\it tran\/},q_0,X,F)$ un autómata de pila determinista. De acuerdo con la construcción vista para obtener la gramática libre de contexto de un autómata de pila dado, tendremos que las producciones de la gramática correspondiente han de ser las siguientes:

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\/}:$ $\{(q',Y_1Y_2\cdots Y_m)\}=\mbox{\it tran\/}(q,e,Y)\ \Rightarrow$

$$[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\/}:$ $\{(q',Y_1Y_2\cdots Y_m)\}=\mbox{\it tran\/}(q,\mbox{\it nil\/},Y)\ \Rightarrow$

$$[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\/}:$ $\{(q',\mbox{\it nil\/})\}=\mbox{\it tran\/}(q,e,Y)\ \Rightarrow\ \left([q,Y,q']\rightarrow e\right)$.

5.

$\forall q\in Q,Y\in\mbox{\it AlfP\/}:$ $\{(q',\mbox{\it nil\/})\}=\mbox{\it tran\/}(q,\mbox{\it nil\/},Y)\ \Rightarrow\ \left([q,Y,q']\rightarrow \mbox{\it nil\/}\right)$.

En este caso, si para una pareja $(q,Y)\in Q\times\mbox{\it AlfP\/}$ se generasen producciones de acuerdo con la regla 3 entonces no se generará ninguna con la regla 2. Similarmente, si se generase una con la 5, no se generarará ninguna con la 4. De aquí resulta que cualquier lenguaje reconocido por una autómata de pila determinista ha de ser generado por una gramática libre de contexto cuyas producciones son de la forma

$$\begin{eqnarray*}A &\rightarrow& \sigma_1A_1 \cdots \sigma_{k-1}A_{k-1} \sigma_{... ...bien }\\ A &\rightarrow& e,\hspace{2ex} e\in\mbox{\it AlfP\/} \end{eqnarray*}$$

Siguiente: Autómatas de pila con Un nivel arriba: Autómatas de pila Anterior: Autómatas de pila y