next up previous contents
Siguiente: Autómatas de pila y Un nivel arriba: Autómatas de pila Anterior: Principios básicos

Reconocimiento de lenguajes

Sea $\mbox{\it AutP\/}=(Q,\mbox{\it Ent\/},\mbox{\it AlfP\/},\mbox{\it tran\/},q_0,X,F)$ un autómata de pila. Una descripción instantánea (DI) es una cadena

\begin{displaymath}q\sigma;\tau\in Q\times\mbox{\it Ent\/}^*\times\mbox{\it AlfP\/}^*\end{displaymath}

que indica que el autómata está en el estado q, se está leyendo el primer símbolo a la izquierda de $\sigma$ y $\tau$ es el contenido de la pila. El símbolo en el tope de la pila es el primero de $\tau$. Diremos que una DI $d_1=q^1\sigma^1;\tau^1$ se sigue de otra $d_0=q^0\sigma^0;Y^0\tau^0$, $\mbox{\it AutP\/}\vdash (d_0\rightarrow d_1)$, si es el resultado de aplicar la transición correspondiente a d0. Formalmente, $\mbox{\it AutP\/}\vdash (d_0\rightarrow d_1)$ si y sólo si

\begin{displaymath}\begin{array}{lcl}
\left[\sigma^0=e^0\sigma^1\right]\land\le...
...\/})\in\mbox{\it tran\/}(q^0,\mbox{\it nil\/},Y^0)
\end{array}\end{displaymath}

La cerradura reflexivo-transitiva de la relación ``se sigue'' es la relación ``se deriva'', denotada como $\mbox{\it AutP\/}\vdash (d_0\stackrel{*}{\rightarrow} d_1)$. La descripción inicial de una palabra $\sigma \in \mbox{\it Ent\/}^*$ es $\mbox{\it DI\/}_0(\sigma)\equiv\left[q_0\sigma;X\right]$. Una DI $d=q\sigma;\tau$ se dice Una palabra $\sigma \in \mbox{\it Ent\/}^*$ se dice Sea $\mbox{\it LF\/}(\mbox{\it AutP\/})$ el lenguaje consistente de las palabras reconocidas por estados finales. Sea $\mbox{\it LPV\/}(\mbox{\it AutP\/})$ el lenguaje consistente de las palabras reconocidas por pila vacía. Ambas nociones de reconocimiento son equivalentes.

Lema 2.1   Para cada autómata de pila $\mbox{\it AutP\/}=(Q,\mbox{\it Ent\/},\mbox{\it AlfP\/},\mbox{\it tran\/},q_0,X,F)$ existe otro autómata de pila $\mbox{\it AutP\/}'=(Q',\mbox{\it Ent\/},\mbox{\it AlfP\/}',\mbox{\it tran\/}',q_0',X',F')$ tal que el lenguaje reconocido por estados finales en el primer autómata es reconocido por pila vacía en el segundo, es decir

\begin{displaymath}\mbox{\it LF\/}(\mbox{\it AutP\/})=\mbox{\it LPV\/}(\mbox{\it AutP\/})'\end{displaymath}

En efecto, $\mbox{\it AutP\/}'$ se construye a partir de $\mbox{\it AutP\/}$ como sigue:
1.
en general, actúese en $\mbox{\it AutP\/}'$ como se hace en $\mbox{\it AutP\/}$,
2.
cuando se llegue a un estado final de $\mbox{\it AutP\/}$, transítese en $\mbox{\it AutP\/}'$ de manera que ahí se vacíe la pila,
3.
para evitar reconocimiento de palabras que incidentalmente vacíen la pila de $\mbox{\it AutP\/}'$, colóquese ahí un nuevo delimitador ``derecho'' X' que no pertenezca al alfabeto $\mbox{\it AlfP\/}$ y bórrese sólo en el caso del paso 2.



Lema 2.2   Para cada autómata de pila $\mbox{\it AutP\/}=(Q,\mbox{\it Ent\/},\mbox{\it AlfP\/},\mbox{\it tran\/},q_0,X,F)$ existe otro autómata de pila $\mbox{\it AutP\/}'=(Q',\mbox{\it Ent\/},\mbox{\it AlfP\/}',\mbox{\it tran\/}',q_0',X',F')$ tal que el lenguaje reconocido por pila vacía en el primer autómata es reconocido por estados finales en el segundo, es decir

\begin{displaymath}\mbox{\it LPV\/}(\mbox{\it AutP\/})=\mbox{\it LF\/}(\mbox{\it AutP\/})'\end{displaymath}

En efecto, $\mbox{\it AutP\/}'$ se construye a partir de $\mbox{\it AutP\/}$ como sigue:
1.
colóquese en $\mbox{\it AutP\/}'$ un nuevo símbolo inicial X',
2.
en general, actúese en $\mbox{\it AutP\/}'$ como se hace en $\mbox{\it AutP\/}$,
3.
cuando se vacíe la pila de $\mbox{\it AutP\/}$, es decir, cuando la marca X' acceda al tope de la pila, transítese en $\mbox{\it AutP\/}'$ a un nuevo estado final.



De ahora en adelante supondremos, sin pérdida de generalidad, que el reconocimiento de un lenguaje con un autómata de pila se hace por pila vacía, y consecuentemente no consideraremos más estados finales.
next up previous contents
Siguiente: Autómatas de pila y Un nivel arriba: Autómatas de pila Anterior: Principios básicos
Guillermo Morales-Luna
2000-06-27