Page 72 - LENGUAJES FORMALES AUTOMATAS Y COMPILADOS

72

Comportamiento de la pila: si el lenguaje es: para N>=0 y la cadena a aceptar fuera
XXXYYY o sea N=3. La pila se comportaría así:

X
X
X
#

#

Al no leer nada, o sea la cabeza de lectura no se mueve en la cinta, no interesa qué cosa hay en la
pila, pasa al siguiente estado e inserta un # en la pila, indicando con esto el final de la pila o el
fondo (en algunos libros se coloca z). Estando en este estado y conteniendo en la pila el #, y, si se
lee una X, al margen de lo que haya en la pila, introduce una X a la pila, así que ahora la pila
contendrá:

X
#

Y se mantendrá en el mismo estado, así sigue leyendo x, hará lo mismo. En consecuencia
contendrá tantos símbolos x, como x haya leído de la cinta de entrada (este es el poder de la
memoria del autómata de pila, la pila. De forma tal que cuando empiece a leer Y’s, ira verificando
si hay X en la pila /transición del segundo al tercer y estando en el tercer estado). O sea irá sacando
cada X a medida que lea cada Y. Esto lo hará hasta que aparezca el fondo de la pila y aceptará la
cadena.

Ejemplo:

Y,X/Λ

X,Λ/X

Y,X/Λ