Fdgf

Cap´ ıtulo 11 Aut´matas de pila o
11.1 Concepto de AP (Aut´matas de pila) o
11.1.1 Definci´n informal o Pushdown-automata (PDA) define Lenguaje independiente de contexto extensi´n de AFND (λ-AFND + pila) o Operaciones de la pila (leer, pop, introducir, push, s´lo s´ o ımbolo superior de la pila) 2 versiones diferentes de aut´matas de pila o 1. AP acepta por estado de aceptaci´n (igual que los AF)o 2. AP acepta por vaciado de pila (estado no importa) Vamos a demostrar que ambos variantes aceptan exactamente los lenguajes independientes de contexto, es decir, se pueden transformar las gramaticas en AP y al rev´s. e En cap´ ıtulos anteriores vimos los AFND, que aceptan todos los lenguajes regulares, pero s´lo un subconjunto de las GIC. Importante es esta parte o por su parecido a unanalizador en un compilador (parser), por tanto, es importante para la construcci´n de compiladores (Qu´ lenguajes pude ser o e reconocidos o no). Empezamos primero con una definci´n informal (Luego definici´n formal). o o Como mencionado anteriormente, el AP es un λ-AFND con una propiedad adicional: una pila para almacenar secuencias o cadenas de car´cteres, llaa mados “s´ ımbolos de pila”. El AP puede, adiferencia de los AFND, almacenar una cantidad infinita de informaci´n. No obstante no tiene acceso aleatorio a los datos (acceso LIFO). o Por tanto, existen lenguajes que pueden ser reconocidos por un ordenador, pero no por un AP.

1

En realidad los AP aceptan todos los lenguajes regulares y los lenguaje independiente de contexto, pero existen muchos lenguajes que no son libre de contexto.Ejemplo de un lenguaje no independiente de contexto: L = {0n 1n 2n |n > 1}, el conjunto de secuencias de car´cteres que consta de 3 grupos de s´ a ımbolos 1, 2 y 3 con el mismo tama˜o. n

Descripci´n: La unidad de control (finito) lee uno por uno los s´ o ımbolos de la entrada. El AP observa el s´ ımbolo superior (y s´lo el s´ o ımbolo superior) de la pila y entra en un estado nuevo (que puedeser el mismo). La transici´n a un nuevo estado depende de: o 1. del estado actual 2. del s´ ımbolo le´ ıdo 3. El s´ ımbolo en la cima de la pila Transiciones λ tambi´n son posibles (sin leer la entrada). e Secuencia de ejecuci´n (transici´n): o o 1. Leer y consumir un s´ ımbolo de entrada. Las transiciones “espont´neas” a λ tambi´n son posibles (sin leer la entrada) e 2

2. Transici´n a unestado nuevo (que puede ser el mismo) o 3. Reemplazar el s´ ımbolo superior de la pila por cualquier cadena Cadena de car´cteres vac´ λ (operaci´n pop) a ıa o La misma cadena de car´cteres (no cambiar la pila) a S´ ımbolo nuevo (pop, seguido por push) Cadena nueva de car´cteres (pop, seguido por push), si |n| > 1, a 1×pop y n-veces push

Ejemplo: Lan bn = {an bn |n ≥ 0} Es un lenguaje independientede context generado por la siguiente gram´tica: a 1. P ::= λ|aP b 2. P ::= λ|aP B; B ::= b (Greibach) 3. P ::= λ|SB; S ::= AP ; A ::= a; B ::= b (Chomsky) Pregunta: ¿C´mo podemos dise˜ar un AP que acepta este lenguaje? o n 1. Empezamos en un estado p0 . En este estado leemos las entradas a y introducimos una marca en el contador. Esta marca sirve como contador: Cuando hemos le´ m(m ≤ n)a′ s,entonces se encuentran m marcas ıdo en la pila. 3

2. Cuando se hayan le´ todos los s´ ıdo ımbolos de entrada a, el aut´mata o cambia al estado p1 . En este estado lee un s´ ımbolo de entrada b y elimina un s´ ımbolo de la pila. 3. Cuando la pila est´ vac´ entonces hemos le´ n smbolos a y postee ıa, ıdo ´ riormente n s´ ımbolos b. 4. Entramos en un nuevo estado p2 y aceptamos la entrada que hab´le´ ıa ıdo completamente. Ejemplo: LwwR = {wwR |w se encuentra en (0 + 1)∗ } Lenguaje, normalmente llamado “w-w-reflejo” de los pal´ ındromos con la misma cantidad de car´cteres sobre el alfabeto {0, 1}. Es un lenguaje indepena diente de context generado por la siguiente gram´tica: a 1. P ::= λ 2. P ::= 0P 0 3. P ::= 1P 1 Pregunta: ¿C´mo podemos dise˜ar un AP que acepta este lenguaje? o n Empezamos...