next up previous contents
Siguiente: Reconocimiento de lenguajes Un nivel arriba: Autómatas de pila Anterior: Autómatas de pila

Principios básicos

Una pila es un dispositivo de almacenamiento que sigue el principio ``primero-en-entrar-último-en salir''. Lo podemos pensar como un arreglo lineal indicado con los números naturales:

\begin{displaymath}\longrightarrow\ \ \framebox[4em]{$c[0]$}\framebox[4em]{$c[1]...
...]{$c[n-1]$}\framebox[4em]{$c[n]$}\framebox[4em]{$c[n+1]$}\cdots\end{displaymath}

La casilla c[0] se dice ser el tope de la pila. En todo momento, Sobre una pila se pueden ejecutar dos operaciones:
Empilar:
Si $\sigma_0$ es una palabra en $\mbox{\it AlfP\/}^*$ y $\sigma\in\mbox{\it AlfP\/}^*$ es el contenido de la pila, entonces la acción $E(\sigma_0,\mbox{\it Pila\/})$ hace que el contenido de la pila sea $\sigma_0\sigma$.
Desempilar:
Si $\sigma_0$ es un prefijo del contenido $\sigma\in\mbox{\it AlfP\/}^*$ de la pila, es decir $\sigma=\sigma_0\sigma_1$ para alguna palabra $\sigma_1\in\mbox{\it AlfP\/}^*$, entonces la acción $D(\sigma_0,\mbox{\it Pila\/})$ hace que el contenido de la pila sea $\sigma_1$.
(Es convencional nombrar a las operaciones E y D por sus denotaciones en inglés: Push y Pop, respectivamente.) Ahora bien, estas dos operaciones pueden realizarse mediante una operación de ``sustitución'' del tope de la pila: $\mbox{\it Sus\/}(\sigma_0,\mbox{\it Pila\/})$ hace que si el contenido de la pila fuese $\sigma_1=s\sigma_2$, donde s es el símbolo actual en el tope de la pila, entonces el contenido vendrá a ser $\sigma_0\cdot\sigma_1$. En otras palabras, el contenido del tope s es sustituído por $\sigma_0$. Así pues la acción $E(\sigma_0,\mbox{\it Pila\/})$ equivale a $\mbox{\it Sus\/}(\sigma_0\cdot s,\mbox{\it Pila\/})$, donde s es el contenido en el tope; en tanto que la acción $D(\sigma_0,\mbox{\it Pila\/})$ es equivalente a reiterar la acción $\mbox{\it Sus\/}(\mbox{\it nil\/},\mbox{\it Pila\/})$ tantas veces como sea la longitud de $\sigma_0$. En el resto de esta sección consideraremos solamente acciones de sustitución en el tope de la pila. Un autómata de pila (no-determinista) es una estructura de la forma

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

donde

\begin{eqnarray*}Q &:& \mbox{\rm es el conjunto de {\em estados},} \\
\mbox{\i...
...bset Q &:& \mbox{\rm es un conjunto de estados {\em finales}.}
\end{eqnarray*}


En cada momento, el autómata funciona como sigue: Si se está en el estado $q\in Q$, se recibe el símbolo $e\in\mbox{\it Ent\/}$ y en el tope de la pila se encuentra el símbolo $Y\in\mbox{\it AlfP\/}$, Ejemplo (Palíndromas): Sea $L=\{\sigma\in (0+1)^*\vert\sigma=\mbox{\it rev\/}(\sigma)\}$ el lenguaje que consta de todas las palabras que son palíndromas. Una estrategia obvia para reconocer palabras en L es la siguiente:
1.
al inicio la pila ha de estar vacía,
2.
se deposita en la pila una copia de ``la primera mitad de la palabra recibida'', es decir,
(a)
con cada 0 que llegue se coloca una marca C en la pila,
(b)
con cada 1 que llegue se coloca una marca U en la pila,
3.
al (suponer) haber llegado la ``primera mitad'' se busca que ``la segunda'' empate con la primera, es decir,
(a)
se pasa a un estado de desempilar,
(b)
con cada 0 que llegue y que empate con una marca C en la pila, se desempila la marca,
(c)
con cada 1 que llegue y que empate con una marca U en la pila, se desempila la marca,
4.
se tendrá éxito sólo si al terminar de leer se tiene vacía la pila.
Así pues, consideremos los conjuntos siguientes:
Alfabeto de entrada:
$\mbox{\it Ent\/}=\{0,1\}$.
Alfabeto de pila:
$\mbox{\it AlfP\/}=\{C,U,A,X\}$. X es la marca del extremo derecho de la pila. C y U son marcas para recontar 0's y 1's, y A es una marca de error.
Estados:
Consideremos 4 estados,

\begin{eqnarray*}q_0 &:& \mbox{\rm inicial} \\
q_1 &:& \mbox{\rm comienza a de...
...aso de pal\'\i ndromas impares,} \\
q_3 &:& \mbox{\rm final}
\end{eqnarray*}


Transiciones:
Las siguientes transiciones se explican por sí solas. Las de la izquierda corresponden a ``buenas computaciones'' de reconocimiento. Las de la derecha marcan errores.

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

En cualquier otra configuración, la función de transición asocia el conjunto vacío.
Ejemplo: Sea $L=\{0^{3n}1^n\vert n\geq 0\}$ el lenguaje que consta de todas las palabras que bien son vacías o bien se inician con 0's, terminan con 1's y contienen el triple de 0's que de 1's. Una estrategia obvia para reconocer palabras en L es la siguiente:
1.
al inicio la pila ha de estar vacía,
2.
con cada 0 que llegue se coloca una marca C en la pila,
3.
al llegar al primer 1 se pasa a un estado de desempilar,
4.
con cada 1 hay que desempilar exactamente 3 marcas C, y
5.
se tendrá éxito sólo si al terminar de leer se tiene vacía la pila.
Así pues, consideremos los conjuntos siguientes:
Alfabeto de entrada:
$\mbox{\it Ent\/}=\{0,1\}$.
Alfabeto de pila:
$\mbox{\it AlfP\/}=\{C,A,X\}$. X es la marca del extremo derecho de la pila. C es una marca para recontar 0's y A es una marca de error.
Estados:
Consideremos 5 estados,

\begin{eqnarray*}q_0 &:& \mbox{\rm inicial} \\
q_1 &:& \mbox{\rm comienza a de...
... cada secuencia de tres $C$ 's,} \\
q_4 &:& \mbox{\rm final}
\end{eqnarray*}


Transiciones:
Las siguientes transiciones se explican por sí solas. Las de la izquierda corresponden a ``buenas computaciones'' de reconocimiento. Las de la derecha marcan errores.

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

En cualquier otra configuración, la función de transición asocia el conjunto vacío.

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