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:

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

La casilla c[0] se dice ser el tope de la pila. En todo momento,

• cada casilla puede estar vacía o contener un símbolo de un alfabeto de pila, $\mbox{\it AlfP\/}$, y
• la pila está en blanco salvo en un conjunto finito de casillas, i.e.
  
  $$\exists n_0\forall n:\ n>n_0\Rightarrow\mbox{\it Contenido\/}(c[n])=\mbox{\it vac\'\i a\/}.$$
  
  
  En este caso, si para cada $i\geq 0$, x_i es el contenido de la casilla c[i], entonces
  • podemos establecer que el símbolo más a la derecha, x_n0, sea un símbolo distinguido X en el alfabeto $\mbox{\it AlfP\/}$ (para marcar el fin de la palabra inscrita en la pila), y
  • decimos que la palabra $\sigma=x_0x_1\cdots x_{n_0-1}$ es el contenido de la pila.

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

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

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\/}$,

• si $(q',\sigma)\in\mbox{\it tran\/}(q,\mbox{\it nil\/},Y)$ entonces se pasa al estado q', se sustituye Y por $\sigma$ y NO se avanza en la cadena de entrada, o bien
• si $(q',\sigma)\in\mbox{\it tran\/}(q,e,Y)$ entonces se pasa al estado q', se opera en la pila según se describe arriba y se avanza una posición a la derecha en la cadena de entrada.

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{array}{\vert\vert c\vert c\vert\vert}\hline\hline \be... ...t\{ (q_3,A) \right\} \end{array} \\ \hline\hline \end{array}$$

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{array}{\vert\vert c\vert c\vert\vert}\hline\hline \be... ...t\{ (q_4,A) \right\} \end{array} \\ \hline\hline \end{array}$$

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

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