EQUIPO 3.- AUTOMATAS PUSH DOWN...

EL MÁGICO MUNDO DE LOS AUTÓMATAS

camp

s- París- 1890
Desde la Grecia antigua existe la noción de autómata: en efecto el término "automatos" significaba "que se mueve por el mismo" y era sinónimo de misterio y fascinación. En Egipto por ejemplo las estatuas articuladas eran utilizadas tanto en la política cómo en la religión.
Estas estatuas articuladas adoraban a Dios y a difuntos de importancia, con dispositivos invisibles a los fieles, y que eran casi siempre originados utilizando aire, colocado en vejigas de animales, que al dilatarse por pequeñas presiones hacían que se moviera la figura.

En la historia de los autómatas, durante el siglo XVIII, se destacan la creación de piezas excepcionales:
Los androides. Estos autómatas con formas humanas son el resultado del genio y la habilidad de creadores magistrales como Vaucanson en Francia y Jaquet-Droz en Suiza.

Jacques de Vaucanson (1709-1782) nacido en Grenoble, tuvo desde joven pasión por la mecánica.
Pierre Jaquet-Drotz (1721-1790) realizó entre otros el famoso "Pierrot écrivain", un fabuloso pierrot que sentado en una mesa, y junto a una lámpara escribe una carta interminable.

Una de las personas que en el mundo ha logrado formar una de las colecciones más interesantes de autómatas es Madame de Galéa (Madeleine de Galéa 1874- 1956). Su colección conformada por 80 espectaculares autómatas, después de su desaparición, es donada por su hijo Christian de Galéa, al Príncipe Rainiero III, en el Principado de Monáco. La misma se encuentra actualmente en el Museo Nacional de Mónaco.

1.1.1 Expresiones Regulares (ER)

Se denomina a un conjunto regular si puede ser generado a partir de un alfabeto £, utilizando tan solo las operaciones de unión, concatenación y cerradura de Kleene.

Definición: Sea £ un alfabeto cualquiera. Las expresiones regulares sobre £ se definen de la siguiente manera:

i) 0, E y a, ¥a E £, son expresiones regulares sobre £.
ii) Sean u y v expresiones regulares sobre £, entonces:

u + v, uv y u* son expresiones regulares sobre £.

iii) Ninguna expresión que no este definida en i e ii, es expresión regular sobre £.

La notación u⁺ = uu*, y u² = uu, u³ = u²u,...
ejemplo:

(a) 00
(b) (0+1)*
(c) (0+1)* 00(0+1)*
(d) (1+ 10)*

1.1.2 Equivalencia entre AFN y Expresiones Regulares

Teorema: Sea r una expresión regular. Entonces existe un AFN con transiciones-E que acepta L(r).

Demostración: Aplicando inducción sobre el numero de operadores en la expresión regular r, se muestra que existe un AFN M, con transiciones-E con un solo estado final, y con transiciones que lo pueden sacar de dicho estado; tal que L(M) = L(r).

Caso base: La expresión r debe ser E, 0 o a para algún a E £.

Inducción: (uno o más operadores)Asumimos que el Teorema es verdadero para expresiones regulares con un número de operadores menos a i, i. Sea r una expresión con i operadores. Existen tres casos:

Caso 1.- r=r1+r2 con r1, r2 que contienen menos de i operadores:

Caso 2.- r=r₁r₂

Caso 3.- r=r₁*

entonces: L(M) = L(M1 ) Lqqd

ejemplo:
01*+1 = 0(1*) + 1

Teorema de Kleene: **Un lenguaje L es aceptado por un AFD, si y solo si, L es un conjunto regular.
Demo: Sea L el conjunto aceptado por el AFD

M= ({q1,...,qn}, £, S, q1, F )

Sea Rkij el conjunto de todas las cadenas x tales que S(q_i,x)=q_j, y si S(q_i,y) = qe, para cualquier y que es un prefijo de x, y E, entonces ek.

Es decir, R^k_ij es el conjunto de cadenas tales que pasan al autómata finito del estado qi al estado qj sin pasar por ningún estado enumerado mayor a k.

Dado que no existe ningún estado enumerado mayor que n, Rⁿ_ij denota todas las cadenas van de q_i a q_j.

Es posible definir R^k_ij de una manera recursiva si procedemos de la siguiente manera:

R^k_ij = R^k-1_ik (R^k-1_kk)* R^k-1_kj U R^k-1_ij

{a | S(q_i,a)= q_j} if ij
R⁰_ij =
{a | }S(q_i,a)= q_j} U {E} if i=j

Debemos demostrar, que para cada i,j y k , existe una expresión regular r^k_ij que denota el lenguaje R^k_ij . Procedamos por inducción sobre k:

Base:
a₁ +a₂ + ....+a_p si ij
r^o_ij = a₁ +a₂ + ....+a_p + E si i=j

en donde {a_1, a₂ ,....,a_p } son todos los símbolos de £ tales que S(q_i,a) = q_j

Si este es un conjunto vacío, entonces:

0 siij
r^o_ij = E sii=j

Inducción: La formula recursiva para Rkij tan solo incluye las generaciones: unión, concatenación y cerradura. Por la hipótesis de inducción, para cada l y m existe una expresión regular rlmk-1 tal que:

L(r_lm^k-1)= R_lm^k-1

Entonces para Rijk podemos elegir la expresión regular:

(r_ik^k-1)(r_kk^k-1)*(r_kj^k-1) + r_ij^k-1

Lo cual completa la inducción.

Para terminar la demostración, solo debemos de observar que:

L(M) = U Rⁿ_ij

Procedimiento para construir una expresión regular a partir de un autómata finito:

Entrada: Diagrama G de un autómata finito. Los nodos se numeran 1,2,....,n.

1. Forme m copias de G, cada una de los cuales contenga tan solo un estado final. Llame a estas gráficas G1,G2,...,Gm. Cada nodo final de G, es el nodo final de Gt, con t=1,2,..,m.
2. Por cada Gt hay que hacer:
   Repita

- Elija un nodo i en Gt que no sea ni nodo de inicio ni nodo final
- Elimine el nodo i de Gt, y haga lo siguiente: Por cada j,k i (es valido j=k) haga:

i) Si w_ji 0, w_ik0 y w_ii = 0 entonces: Agregue un arco del nodo j al k, etiquetado w_ji w_ik.

ii)Si w_ji0, w_ik0 y w_ii0 entonces: Agregue un arco del nodo j al nodo k etiquetado w_ij(w_ii )* w_ik.

iii)Si j y k tienen arcos etiquetados w₁,w₂,..,w_s, reemplácelos por un nuevo arco etiquetado w₁+w₂+...+w_s

iiii) Remueva el nodo i y todos los arcos que incidan sobre el en Gt.

Hasta: los únicos nodos en Gt, sean el nodo de inicio y el del estado final.
Determine la expresión aceptada por Gt.

La expresión regular aceptada por G, se obtiene al unir las expresiones de cada Gt con t.

La eliminación del nodo i se logra encontrando todas aquellas rutas j,i,k de longitud 2 que tienen i como nodo intermedio.

Pumping Lemma(para lenguajes Regulares)

Sea L un lenguaje regular, que es aceptado por un AFD con k estados. Sea z una cadena en L cuya longitud |z|k. Entonces z puede ser reescrito como: z=uvw en donde: |uv|k, |v|>0 y uv²w E L, , ¥i0.

El llamado Pumping Lemma, es una herramienta poderosa para demostrar que un lenguaje no es regular.

Ejemplo:

(1) L={z E {a,b}* | |z| =n², para algún n E N}

Supongamos que existe un AFD que reconoce L, y sea k el numero de estados que contiene. Por el Pumping Lemma, toda z E L con |z|k puede descomponerse como uv²w^.

Considérese una cadena |z|=k², por el Pumping Lemma existen u,v y w con 0<|v| entonces:

|uv²w|= |uvw|+ |v| = k²+|v|k²+k < k² +2k +1 = (k+1)²

entonces:

|uv²w| no puede ser un cuadrado perfecto ---> L no es un lenguaje regular.

(2) El lenguaje L={aⁱ | i es un primo} es no regular, sea n un primo y n>k, -->aⁿ = uvⁱw

Supongamos: |uvⁿ⁺¹w|= |uvwvⁿ| = |uvw| + |vⁿ| = n + n (|v|) = n(1+|v|)

entonces:

El lenguaje es no regular

2 AUTÓMATAS FINITOS (AF)

Autómata Finito.- Modelo de computación muy restringido, sin embargo tiene una gran aplicación en reconocimiento de patrones.

Representa la maquina más simple, y no contiene MEMORIA AUXILIAR. El AF, consiste de una cinta de entrada y una unidad de control.

Funcionamiento: Un AF recibe su entrada como una cadena de caracteres; dicha cadena le es entregada en la cinta de entrada. El AF no genera ninguna salida, excepto alguna SEÑAL que indique que la cadena de caracteres ha sido aceptada.

Un AF es considerado un dispositivo reconocedor de lenguaje.

El lenguaje aceptado por un AF es el conjunto de cadenas que acepta.
Para describir formalmente el funcionamiento de un AF sobre una cierta cadena, debemos extender la definición de nuestra función de transición S, para que se aplique a un estado, y a una cadena de caracteres, en lugar de a un solo símbolo.
Definimos así, la función: K x £* ---> K, la intención es que(q,w) represente el estado del AF después de haber leído w, a partir del estado q.

Definición formalmente:

1)(q,E) = q
2)(¥w E String)(¥a E £) (q, wa)= ((q,w), a)

Así:(1) afirma que sin leer un símbolo, es AF no puede cambiar de estado.

Definición: Un string x se dice que es aceptado por un autómata finito M(K,£,,qo,F) si S(qo,x)=p E F.

Definición: El lenguaje aceptado por M, designado L(M), es el conjunto {x| S(qo,x)E F}.

Definición: Un lenguaje es un conjunto regular(o regular) si consiste en el conjunto aceptado por algún autómata finito.

Ejemplos:

(1) Diseñe un AF para reconocer expresiones aritméticas de longitud arbitraria que comprenden enteros positivos separados por los signos de suma, resta, multiplicación o división.

Q = {0,1}
??={0,1,2,3,4,5,6,7,8,9,+,-,· ,:}
q0 = {0}
F = {1}

(0,1+27:3-2) |--- (1,+27:3-2) |--- (0,27:3-2) |--- (1,7:3-2) |--- (1,:3-2) |--- (0,3-2) |--- (1,-2) |--- (0,2) |--- (1,?)

(2) A =
Q = {0,1,2,3}
??={a,b}
F = {3}
qo = {0}

Tabla 2.1.1 Expresiones aritméticas de longitud arbitraria (Componentes).

2.1.1 Autómata Finito Determinístico(AFD)

Es un autómata finito, y es deterministico cuando su operación esta completamente determinada por su entrada.

Autómata Finito Deterministico: Es un quíntuplo: M=(K, £, S, s, F).

Donde:

k es un conjunto finito de estados (identificadores)
£ es un alfabeto finito (entrada)
s E k es el estado inicial
F subconjunto k es el conjunto de estados finales.
S: k x £ --->, es una función de transición de estados.

Una configuración es la situación en que se encuentra la máquina en un momento dado.

Definición. [q₁,w_1] a _M [q₂,w_2] ssi w₁=s w₂ para un s Î S , y existe una transición en M tal que d (q₁, s )=q₂

Definición. Una palabra w Î S * es aceptada por una máquina M=(K, S , d ,s, F ) si existe un estado q Î F tal que [s,w] a _M* [q, e ]

Definición. Un cálculo en una máquina M es una secuencia de configuraciones c₁,c₂,...,c_n tales que c_i a c_i+1.

Teorema. Dados una palabra w Î S * y una máquina M, sólo hay un cálculo

[s,w] a _M... a _M[q, e ] .

Definición. Dos autómatas M₁ y M₂ son equivalentes, M₁ » M₂ , cuando aceptan exactamente el mismo lenguaje.

Definición. Dos estados son compatibles si ambos son finales o ninguno es final.

Definición. Dos estados q₁ y q₂ son equivalentes, q₁ » q₂ , si al intercambiarlos en cualquier configuración, no se altera la aceptación o rechazo de toda palabra.

Ejemplo:

AFD

Cinta de entrada

Cabeza lectura
Control Finito

Características:

• Cinta dividida en cuadros, con capacidad para un símbolo por cuadro.
• La unidad de proceso es llamada control finito(CF) y puede estar en uno de varios estados(qo,...)
• El CF puede leer el símbolo escrito en cualquier posición de la cinta, utilizando su cabeza lectora movible.
• Al inicio la cabeza lectora se posiciona en el cuadro de mas a la izquierda de la cinta y el CF es situado en su estado inicial(normalmente qo).
• El AF puede leer solo un símbolo a la vez y posiblemente cambiar de estado. Una vez leído un símbolo, la cabeza lectora se posiciona automáticamente en el cuadrado siguiente, hacia la derecha. De esta manera el siguiente movimiento leerá el símbolo en el siguiente cuadro de la cinta de entrada. El proceso se repite continuamente.

• Un símbolo es leído.
• La cabeza se mueve un cuadro hacia la derecha.
• El estado del AUTOMATA cambia.

• Cuando el final de la cadena es alcanzado, el AUTOMATA indica su aceptación o rechazo, de la cadena de caracteres, por el estado en el cual se encuentra al alcanzar el final. Si dicho estado pertenece a uno de los estados finales, la cadena de entrada se acepta, caso contrario se rechaza.

Un Autómata Deterministico: NO puede mover su cabeza lectora hacia atrás.
Una configuración de un AFD es un elemento de k x £*.

Ejemplo:

M=(K, £, S, s, F)

sean

k= {qo,q1}
£={a,b}
s=q_o
F={q_o}

q G S(q,S)
q_o a q_o
q_o b q₁
q₁ c q₁
q₁ d q_o

Definimos una función d de KxS * ® K de la siguiente manera

d (q,e )

d (q,wa) = d ( d (q,w), a )

La intención es que d (q,w) represente al estado en que estará el AF después de leer la cadena w del estado q.

Definición. Un AFN es un quíntuplo (K, S , D ,s, F ) donde K, S , s, F tienen el mismo significado que para el caso de los AFD, y D , llamada la relación de transición, es un subconjunto finito de k xS *x k.

Definición. Una palabra w es aceptada por AFN si existe una trayectoria en su diagrama de estados, que parte del estado inicial y llega a un estado final, tal que la concatenación de las etiquetas de las flechas es igual a w.

Definición. La cerradura al vacío de cerr-e (q) de un estado q es el conjunto más pequeño que contiene al estado q, a todo estado r ' $ una transición (p,e ,r) Î D , con cerr-e (q).

Definición. Para todo AFN existe algún AFD tal que L(N)=L(D).

Modificando el modelo del AF para que acepte cero, una o más transiciones para un mismo símbolo de entrada, obtenemos el AFN.

Una secuencia de entrada a1,a2,....an, es aceptada por un AFN si existe una secuencia de transiciones correspondientes a la secuencia de entrada, que conduce del estado inicial (a un estado final).

Como se vera mas adelante, cualquier conjunto aceptado por un autómata no determinístico puede ser aceptado por un AFN.

Un AFN se denota formalmente por un quíntuplo:

(K, £, S, q_o, F) donde:

k,£,q_o,Fson estados, alfabeto, estado inicial y estados finales y tienen el mismo significado que en el AF pero S:k x £ ---->2^k

Ejemplo:

Un AFN que acepte todas las cadenas que contengan dos ceros consecutivos o dos unos consecutivos.
Ejemplo: Tomando el AFND.

Q = {0,1,2,3}
??={a,b}
F = {3}
qo = {0}

Q' = {[0],[1],[2],[3],[01],[02],[03],[12],[13],[23],[012],[013],[023],[123],[0123]}
q0' = [0]
F' = {[3],[03],[13],[23],[013],[023],[123],[0123]}

Reemplazando:
[0] por q0
[01] por q1
[02] por q2
[013] por q3
[012] por q4
[023] por q5
y [0123] por q6

Ejemplo :

• (q0,aababaa) |--- (q1,ababaa) |--- (q3,babaa) |--- (q4,abaa)) |--- (q6,baa) |--- (q6,aa) |--- (q6,a) |--- (q6,?)
• 
  (q0,bba) |--- (q2,ba) |--- (q5,a) |--- (q4,?)

2.1.3 Equivalencias entre los AFD's y los AFN's

Dado que todo AFD es un AFN, es claro que la clase de lenguajes aceptado por los AFN's incluye los aceptados por los AFD. AFNAFD.

Teorema: Sea L un lenguaje aceptado por un AFN. Entonces existe un AFD que acepta L.

Demo: Sea M=(K, £, S, q_o, F) un AFN que acepta el lenguaje L.
Definamos un DFA, M'=(K', £', S', q_o^', F') de tal manera que:
(1) Los estados de M' son todos subconjuntos del conjunto de estados de M. Esto es: K' = 2^k = P(K) los nombres de dichos conjuntos se generara de la siguiente manera:

[q₁,...,q_i] E K' para {q₁,...,q_i} K

(2)F' es el conjunto de todos los estados en K' que contenga algún estado que pertenezca a F.
(3) q_o'=[q_o]
(4)Definimos S'([q₁,q₂,...,q_i], a) = [P₁, P₂, ....,P_j]
si y solo si: S({q₁,...,q_i}, a) = {P₁, P₂, ....,P_j}

Demostramos ahora por inducción sobre la longitud de la cadena de entrada, que:

S'(q₀',x) = [q₁,...,q_i]
si y solo si: S(q_o,x) = {q₁,...,q_i}

Demo:

1) Para |x|= 0, x=E

S'(q₀',E) = [q₀]
S(q₀,E) = {q₀}

2) H.I, |x|=m

S'(q₀',x) = [r₁,r₂,...,r_n]
<--->S(q₀,x) = {r₁,r₂,...,r_n}

3) Demostrar para |w| = |xa|= m+1
S'(q₀',xa) = S'(S'(q₀',x),a)

Por definición de S' tenemos:

S'([r1,r2,...,rn], a) = [P1,P2,...,Pj]
S({r1,r2,...,rn}, a) = {P1,P2,...,Pj}

Así tenemos que:

S'(S'(q₀',x),a) = S'([r₁,r₂,...,r_n] , a) = [P₁,P₂,...,P_j]
<------> S(S(q₀',x), a) = S({r₁,r₂,...,r_n }, a) = {P₁,P₂,...,P_j} Lqqd.

entonces AFN = AFD

2.1.4 Autómata Finito No Deterministico con movimientos E

Definición: Un autómata finito no deterministico con movimientos-E consiste en un quíntuplo (k , £, S, q_0, F ) en donde K, £, q_0, F se definen de la misma manera que el autómata finito no deterministico, y con:

S: K x (£ U {E})----> 2^k la intención es que S(q,a)consista de todos los estados Pj, tales que existe una transición etiquetada a, desde q hasta Pj. En donde a es el símbolo E o cualquier símbolo es £.

Función de transición del ejemplo anterior:

Definición: Denominamos CERRADURA - E(q) a todos aquellos vértices (estados) Pj, tales que existe una ruta de p a q, consistente en transiciones E.

Ejemplo:

CERRADURA-E(qo) = {q₀,q₁,q₂}

Definición: Llamamos CERRADURA-E(q) al conjunto de todos los nodos p tales que existe una ruta de q a p etiquetada E.

Es fácil extender esta definición a la CERRADURA-E(p) en donde p es un conjunto de estados:

Sea U CERRADURA-E(q), definamos como:

(1)(q,E) = CERRADURA-E(q)

(2) Para w E £* y a E £,

(q,wa)= CERRADURA-E(p)

en donde P = {p| para algún v E (q,w)y p E S(r,a)}

Es conveniente extender S y a conjuntos de estados de la manera siguiente:

(1) S(R,a) = U_{q en R} S( q ,a)

(2) (R,w)= U_{q en R}( q ,a)
para conjuntos de estados R.

Definamos: L(M) el lenguaje aceptado por M=(Q,£, S, q_0, F) (un AFN con movimientos E):

L(M) = {w| (q_0,w) ^ F 0}

Equivalencia entre un AFN y un AFN con Movimientos-E

Teorema: Si L es aceptado por un AFN con movimientos-E entonces L es aceptado por un AFN sin movimientos-E.

Demo: Sea M =(Q, £, S, q_o, F) un AFN con Movs-E. Construya un M' = (Q, £, S', q_o, F')
donde:

y S'(q,a) = (q , a) para q E Q y a E £. Resta demostrar por inducción sobre |x| que S'(q_o,x)=(q_o,a) por definición de S'.

Inducción: |x| > 1, sea x=wa, a E £ entonces:

S'(qo,wa)= S'(S'(qo,w),a)

Por hipótesis de Inducción

S'(qo,w)= (q_o,w)

Sea (qo,w)=P, por demostrar S'(p,a)= (q_o,wa)

S'(p,a)= U S'(q,a) = U (q,a)

Entonces, como P= (q_o,w) tenemos:

U (q,a) = (qo,wa) por la regla z en la definición de
S'(q_o,wa) = (q_o,wa)

3 CONCEPTO DE AUTÓMATA DE PILA (PUSHDOWN).

Un autómata de pila (APN) es una máquina de estados finito al que se le añade una memoria externa en forma de pila (stack), es decir que sólo acepta operaciones meter (push) y sacar (pop).

Definición: Un autómata de pila es un autómata finito más una pila. Se de definen por la a tupla

M = (Q; P ; ¡; ±; q0; Z0; F)

donde Q; P,S , q₀ y F se definen igual que en un AFN. G es un alfabeto de los caracteres que pueden introducirse a la pila, y Z₀ es el símbolo inicial en la misma, generalmente l (significa pila vacía), pero en ocasiones es útil usar otro símbolo. La función de transición es definida como:

• : Q x (S È {l } ) x (G È {l } ) ® [Q x (G È {l })]*

es decir que el cambio de estado ya no sólo depende del estado y del símbolo en la entrada, sino además del contenido de la pila, específicamente del símbolo en el tope de la pila. El contenido de la pila puede cambiar después de cada transición.

Para clarificar a la función de transición, analicemos la parte por parte:

Q x (S È {l } ) x (G È {l } ): Esta nos dice que los elementos del dominio son tercias (estado, alfabeto, pila)

[Q x (G È {l })]*:Indica que el codominio son varios pares del tipo (estado, pila)

Ejemplo 63 d (q_i, a, A) = {[ q_J, B ] } Para realizar esta transición es necesario estar en el estado q_i, estar analizando una a en la cadena de entrada y tener en el tope de la pila una A. Al realizarse la transición pasamos del estado q_i al q_J , se procesa el símbolo a, sacamos A de la pila y metemos B .

Transición (q_i, a, A) = {( q_j, B)}

En el diagrama de transición, A/B significa que se reemplaza una A en el tope de la pila por una B. El significado de l ¸ es de cuidado especial, ya que en ocasiones puede significar "pila vacía", pero más generalmente significa "no importa lo que hay en la pila". Existen tres transiciones especiales que generan una acción en particular, estas son:

1. d (q_i, l , A ) =[ q_i, l ] En esta transición la única acción que ocurre es desapilar A.
2. d (q_i, l , l ) =[ q_i, A] La única acción que ocurre es apilar A.
3. d (q_i, a, l ,) =[ q_i, l ] Equivale a una transición de AF normal. (como si no tuviera pila)

3.1 Teoremas para los autómatas de pila (Push Down).

Definición: Un AP determinista se define como el AP (K,S ,G ,D ,s,F) tal que para cada tripleta (p,x,y) en KxS xG , existe una y solo una transición en D de la forma (p,u,v;q,z), donde (u,v) Î { (x,y),(x, e ),(e ,y),(e ,e ) }, q Î K, z Î G

Teorema. Si L₁ es un LLC y L₂ es un LR, entonces L₁ Ç L₂ es un LLC.

Teorema. Todo lenguaje aceptado por un AF es también aceptado por un AP.

Teorema. Si L es un LLC entonces hay un AP M tal que L(M)=L

De la construcción del AP descrito anteriormente, concluimos la siguiente proposición:

S® *w ssi [p,w,e ] a * [q,e ,e ]

Si L₁ y L₂ son LLC entonces existe un AP que acepta L_1È L₂

3.2 Autómatas de Pila y lenguajes libres de contexto.

Los autómatas de pila son máquinas que nos permiten aceptar lenguajes libres de contexto. Los autómatas de pila son máquinas finitas que tienen una memoria que les da la capacidad de "recordar". De esta manera es posible reconocer lenguajes del tipo aⁱbⁱ | i >= 0, en el que se necesita saber cuantas a’s tiene la palabra para determinar si el número de b’s es igual.

3.3 Clasificación de Autómatas Push Down

1. Autómatas a pila embebidos
2. Autómatas a pila embebidos ascendentes
3. Autómatas lógicos a pila restringidos
4. Autómatas lineales de índices
5. Autómatas con dos pilas

3.3.1 Autómatas a pila embebidos

En los cuales la estructura principal de almacenamiento la constituye una pila de pilas. Junto a la definición clásica se presenta una nueva formulación en la cual se elimina el control de estado finito y se simplifica la forma de las transiciones al tiempo que se mantiene la potencia expresiva. Esta nueva formulación permite diseñar una técnica de tabulación para la ejecución eficiente de los diversos esquemas de compilación para gramáticas de adjunción de árboles y gramáticas lineales de índices.

3.3.2 Autómatas a pila embebidos ascendentes

Constituyen los autómatas a pila embebidos ascendentes. En este capítulo se realiza una definición formal de los mismos, algo que no se había logrado hasta el momento. La eliminación del control de estado finito permite simplificar la forma de las transiciones, lo cual facilita la definición de una técnica de tabulación para este modelo de autómata.

3.3.3 Autómatas lógicos a pila restringidos

Las gramáticas lineales de índices constituyen un tipo específico de gramáticas de cláusulas definidas en el cual los predicados tienen un único argumento en forma de pila de índices. Aprovechamos esta característica para definir una versión restringida de los autómatas lógicos a pila adecuada al tratamiento de este tipo de gramáticas y de las gramáticas de adjunción de árboles. Dependiendo de la forma de las transiciones permitidas, podemos distinguir tres tipos diferentes de autómata, uno que permite el análisis ascendente de los índices o adjunciones, otro que permite el análisis descendente y otro que permite estrategias mixtas. En los dos últimos casos es preciso establecer restricciones en la combinación de las transiciones para garantizar que dichos autómatas aceptan exactamente la clase de los lenguajes de adjunción de árboles. Se presentan esquemas de compilación y técnicas de tabulación para los tres tipos de autómata.

3.3.4 Autómatas lineales de índices

Los autómatas lineales de índices, que utilizan la misma estructura de almacenamiento que los autómatas lógicos a pila restringidos pero con un juego diferente de transiciones. Distinguimos tres tipos diferentes de autómata: los autómatas lineales de índices orientados a la derecha para estrategias en las cuales las pilas de índices se evalúan de modo ascendente, los autómatas lineales de índices orientados a la izquierda en los cuales las pilas de se evalúan de modo descendente y los autómatas lineales de índices fuertemente dirigidos que permiten definir estrategias mixtas de análisis para el tratamiento de las pilas de índices.

3.3.5 Autómatas con dos pilas

Se opta por un modelo de autómata con una nueva estructura de almacenamiento. Se preserva la pila de los autómatas a pila tradicionales, a la que acompaña una pila auxiliar cuyo contenido restringe el conjunto de transiciones aplicables es un momento dado. Los autómatas con dos pilas fuertemente dirigidos permiten definir esquemas de compilación arbitrarios para gramáticas de adjunción de árboles y gramáticas lineales de índices. Por su parte, los autómatas con dos pilas ascendentes sólo permiten describir esquemas de compilación que incorporan estrategias ascendentes en lo referente al tratamiento de las adjunciones y de las pilas de índices. Se presentan las técnicas de tabulación que permiten una ejecución eficiente de ambos modelos de autómata.

3.4 El funcionamiento típico de un autómata pushdown.

Por ejemplo, el siguiente autómata de pila reconoce L(G) = {wcw^R|w E (0+1)*} , es decir los palíndromes en (0 + 1)* cuyo punto intermedio está marcado con un carácter especial c:

M = ({q1,q2}, {0,1}, {RBG}, d , q1, R, q )

Donde d vale:

Figura 3.4.1.- Descripción del valor de d .

1. Descripción

[q, w, a ] ^ [q_j,v,b ] ^ * ^ +

Se pueden usar descripciones instantáneas para ver el funcionamiento del

autómata:

(q, aw, za ) ^ (p,w,b a )

si d (q,a,z) = (p,b ).

La cadena de un lenguaje es aceptado por el autómata si éste para en el

estado final:

L(M) = {w|(q_0,w_,Z₀) ^ (p,e ,g ) para algún p Î F, g Î G *}

3.4.1 Autómata Pushdown para el reconocimiento de lenguajes libres de contexto.

Toda gramática GLC puede ponerse en forma normal de Greibach, en donde todas las producciones son del tipo

L -> aa donde a Î (V U T)*, a Î (T U {e }).

Método de normalización:

1. Suponer V = { L ₁ ... L _m}.
2. Hacer todas las producciones del estilo

L _i -> L _jg para j > i.

Si j < i, sustituir L _j por sus lados derechos. Si j = i, eliminar recursión a la izquierda, sustituyendo: L _i -> L a ₁ | L a ₂ | ... | L _{ia 1} || b ₁ | .... |b _n | por:

L _i -> b ₁ | .... |b _s | b ₁B| .... |b _s B_i

B_i -> a ₁ |a ₂| .... |a _T | a ₁B_i| a ₂B_i| .... |a _T B_i

3. Sustituir L _m -> g en L _m-1, después en L _m-2 y así sucesivamente.
4. En las nuevas producciones B_i, si es necesario sustituir el primer símbolo no terminal por lo que produce.

Por ejemplo en:

G = ({L ₁; L ₂; L ₃ },{a,b},P, L ₁)

P : L ₁ -> L _{2L 3}

L ₂ -> L _{3L 1} | b

L ₃ -> L _{1L 2} | a

hay que cambiar la última producción en

L ₃ -> L _{1L 2} | a

L ₃ -> L _{2L 3L 2} | a

L ₃ -> L _{3L 1L 3L 2} | bL _{3L 2} |a

y después de eliminar la recursión a la izquierda tenemos

L ₃ -> bL _{3L 2}B₃ | aB₃ | bL _{3L 2} | a

B₃ -> L _{1L 3L 2} | L _{1L 3L} 2B₃

Finalmente sólo nos resta sustituir en toda producción, a partir de L ₃, los símbolos no terminales de la izquierda:

L ₁ -> b L ₃ | b L _{3L 2} B _{3L 1L 3} | aB_{3L 1L 3} | b L _{3L 2L 1L 3} | aL _{1L 3}

L ₂ -> b | b L _{3L 2}B_{3L 1} | aB_{3L 1} | b L _{3L 2L 1} | aL ₁

L ₃ -> b L _{3L 2}B₃ | aB₃ | b L _{3L 2} | a