next up previous contents
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

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

donde se cumplen las siguientes dos propiedades: En símbolos,

\begin{displaymath}\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}\end{displaymath}




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$

\begin{displaymath}[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)}]\end{displaymath}

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$

\begin{displaymath}[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)}]\end{displaymath}

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*}



next up previous contents
Siguiente: Autómatas de pila con Un nivel arriba: Autómatas de pila Anterior: Autómatas de pila y
Guillermo Morales-Luna
2000-06-27