Cap´ıtulo 10

Aut´ omatas con dos pilas En este cap´ıtulo se presenta un nuevo modelo de aut´omatas para el an´alisis de los lenguajes de adjunci´on de a´rboles, basado en la utilizaci´on de dos pilas que act´ uan coordinadamente. Las aportaciones de este cap´ıtulo se refieren a la definici´on de los aut´omatas con dos pilas fuertemente dirigidos y a la definici´on de los aut´omatas con dos pilas ascendentes, junto con las t´ecnicas de tabulaci´on para ambos. Este cap´ıtulo est´a basado en [53, 21, 54].

10.1.

Introducci´ on

En los cap´ıtulos anteriores se han definido diversas extensiones de los aut´omatas a pila que aceptan la clase de los lenguajes de adjunci´on de a´rboles. B´asicamente, tales extensiones consisten en asociar a los elementos de la pila del aut´omata una pila de ´ındices. En los aut´omatas l´ogicos a pila restringidos y en los aut´omatas lineales de ´ındices esta caracter´ıstica est´a en la propia definici´on del modelo. En el caso de los aut´omatas a pila embebidos y su variante ascendente esta caracter´ıstica est´a tambi´en presente, aunque de modo impl´ıcito: la cima de cada una de las pilas individuales juega el papel de s´ımbolo de pila mientras el resto de cada pila juega el papel de pila de ´ındices asociada a dicho s´ımbolo. En este cap´ıtulo ofrecemos un enfoque diferente, puesto que en lugar de trabajar con una pila de s´ımbolos de pila asociados a pilas de ´ındices, trabajaremos con dos pilas, una equivalente a la pila de los aut´omatas a pila originales, y otra en la que se almacenan, en principio, ´ındices, de tal modo que los elementos almacenados en esta segunda pila restringen los movimientos que se pueden realizar sobre la primera. Una manera com´ un de simular una m´aquina de Turing consiste en definir un aut´omata a pila que trabaja sobre dos pilas. Ser´a, por tanto, necesario definir cuidadosamente el conjunto de transiciones permitido con el fin de dise˜ nar modelos de aut´omatas con dos pilas que acepten exactamente los lenguajes de adjunci´on de a´rboles. En lo que resta de cap´ıtulo, se describen los aut´omatas con dos pilas tal y como fueron originalmente descritos por Becker [25], para continuar luego con la definici´on de los aut´omatas con dos pila fuertemente dirigidos [53] y los aut´omatas con dos pilas ascendentes [54].

10.2.

Aut´ omatas con dos pilas

Becker define en [25] los aut´omatas con dos pilas (2–Stack automata, 2–SA) como una extensi´on de los aut´omatas a pila en la que se permite realizar las siguientes operaciones: Leer un terminal de la cadena de entrada. 333

334

Aut´ omatas con dos pilas Apilar un s´ımbolo de pila en la primera pila. Eliminar de la primera pila el s´ımbolo situado en su cima. Apilar un s´ımbolo en la segunda pila. Situar en la cima de cada pila un s´ımbolo especial denominado separador . Eliminar de la cima de las dos pilas el s´ımbolo separador. En el caso de que en la cima de primera pila se encuentre un separador, eliminar de la segunda pila el s´ımbolo situado en su cima

Formalmente, definiremos un aut´omata con dos pilas como una tupla (Q, VT , VS , δ, q0 , , $0 ), donde: Q es un conjunto finito de estados. VT es un conjunto finito de s´ımbolos terminales. VS es un conjunto finito de s´ımbolos de pila. q0 es el estado inicial. 6∈ VS es el s´ımbolo separador. $0 ∈ VS es el s´ımbolo inicial de ambas pilas. δ es un conjunto finito de transiciones de alguno de los tres tipos siguientes: (q 0 , α1 , Z2 α2 ) ∈ δ(q, a, Z1 , Z2 ) (q 0 , , α3 ) ∈ δ(q, a, , Z3 ) (q 0 , , ) ∈ δ(q, a, , ) donde q, q 0 ∈ Q, a ∈ VT ∪{}, Z1 , Z3 ∈ VS , Z2 ∈ VS ∪{ }, α1 , α2 ∈ VS∗ ∪VS VS∗ cumpli´endose adem´as que α1 incluye un separador si y s´olo si α2 tambi´en lo incluye, y α3 ∈ VS∗ . El primer tipo de transiciones permite apilar elementos en la primera y/o segunda pila y extraer elementos de la primera pila. Las transiciones del segundo tipo permiten extraer s´ımbolos de la segunda pila si y s´olo si la cima de la primera pila est´a ocupada por un separador. El tercer tipo de transiciones permite eliminar los separadores de la cima de ambas pilas. La configuraci´ on de un aut´omata con dos pilas en un momento dado viene definida por la tupla (q, Υ1 , Υ2 , w), donde q ∈ Q indica el estado en el que se encuentra, Υ1 , Υ2 ∈ ( VS∗ )∗ es el contenido de la primera y segunda pila. El cambio de una configuraci´on a otra viene determinado por la aplicaci´on de una transici´on, de tal modo que si (q, Υ1 Z1 , Υ2 Z2 , aw) es una configuraci´on y (q 0 , α1 , α2 ) ∈ δ(q, a, Z1 , Z2 ) es una transici´on, entonces el aut´omata con dos pilas pasa a la nueva configuraci´on (q 0 , Υ1 α1 , Υ2 α2 , w). Este hecho se denota mediante (q, Υ1 Z1 , Υ2 Z2 , aw) ` (q 0 , Υ1 α1 , Υ2 α2 , w) ∗

Denotamos por ` el cierre reflexivo y transitivo de `. El lenguaje aceptado por pila vac´ıa por un aut´omata con dos pilas viene determinado por el ∗

conjunto de cadenas w ∈ VT∗ tal que (q0 , $0 , $0 , w) ` (q, , , ) para cualquier q ∈ Q. Los aut´omatas con dos pilas tal y como han sido definidos aceptan exactamente la clase de los lenguajes de adjunci´on de a´rboles. Para demostrarlo nos basaremos en la equivalencia entre los 2–SA y los aut´omatas a pila embebidos definidos en el cap´ıtulo 6.

10.2 Aut´ omatas con dos pilas

335

Teorema 10.1 Los lenguajes aceptados por los aut´ omatas con dos pilas son un subconjunto de los lenguajes de adjunci´ on de a ´rboles. Demostraci´on: Siguiendo la demostraci´on de Becker en [25], dado un aut´omata con dos pilas A = (Q, VT , VS , δ, q0 , , $0 ), construiremos un aut´omata a pila embebido con estados E = (Q0 , VT , VS0 , δ 0 , q00 , Q0F , $0 ) tal que VS0 = VS ∪ {]}, los estados en Q0 ser´an triples hq, Si , Z2 i con q ∈ Q, Z2 ∈ VS ∪ {]}, q00 = hq0 , S1, $0 i y las transiciones en δ 0 se construir´an a partir de las transiciones en δ de tal modo que: Si = S1 si la cima de la primera pila del 2–SA no es un separador. La cima del EPDA equivaldr´a a la cima de la primera pila del 2–SA y las pilas unitarias del EPDA situadas inmediatamente debajo de su cima representar´an a los elementos de la segunda pila del 2-SA situados por encima del u ´ltimo separador. El resto de las pilas del EPDA repetir´an esta representaci´on para la siguiente porci´on de las pilas del 2–SA situada entre dos separadores. Si = S2 si la cima de la primera pila del 2–SA es un separador. La cima del EPDA contendr´a la cima de la segunda pila del 2–SA. Para ello, transformaremos cada transici´on (q 0 , α1 , Z2 α2 ) ∈ δ(q, a, Z1 , Z2 ), con Z1 ∈ VS , α1 ∈ VS∗ y α2 = Y1 Y2 . . . Ym , en la transici´on (hq 0 , S1 , Ym i, Y1 Y2 . . . Ym , α1 , ) ∈ δ 0 (hq, S1 , Z2 i, a, Z1 ) En el caso de que α1 = β1 β2 y α2 = Y1 . . . Yk Yk+1 . . . Ym , la transici´on resultante del EPDA ser´a (hq 0 , s1 , Ym i, Y1 . . . Yk , β1 , [], Z2 ] Yk+1 . . . Ym ]β2 ) ∈ δ 0 (hq, S1 , Z2 i, a, Z1 ) donde ] es un s´ımbolo especial que representa el separador del 2–SA y [], Z 2 ] es un s´ımbolo especial que codifica la anterior cima de la segunda pila del 2–SA, con el fin de poder recuperarla posteriormente. En el caso de que Z1 = y α2 = Y1 . . . Ym , la transici´on del EPDA ser´a (hq 0 , S2 , Ym i, , , Y1 . . . Ym ) ∈ δ 0 (hq, S2 , Z2 i, a, Z2 ) Adicionalmente, para todo a ∈ Q crearemos las transiciones (hq, S2 , Z2 i, , , ) ∈ δ 0 (hq, S1 , Z2 i, , ]) que permiten comenzar a manipular la segunda del 2–SA cuando en la cima de la primera est´a un separador. Tambi´en ser´a preciso a˜ nadir, para todo q ∈ Q, las transiciones (hq, S1 , Z 0 i, , , ) ∈ δ 0 (hq, S2 , Z2 i, , [], Z 0 ]) que permiten terminar la manipulaci´on de la segunda pila del 2–SA cuando lleguemos a tener un separador en la cima de la misma. 2

Teorema 10.2 Los lenguajes de adjunci´ on de a ´rboles son un subconjunto de los lenguajes aceptados por los aut´ omatas con dos pilas. Demostraci´on:

336

Aut´ omatas con dos pilas La demostraci´on propuesta en [25] de que todo EPDA puede ser transformado en un 2–SA equivalente es err´onea1 , por lo que plantearemos aqu´ı una versi´on modificada de la misma. Dado un aut´omata a pila embebido con estados E = (Q, VT , VS , δ, q0 , QF , $0 ) construiremos un aut´omata con dos pilas A = (Q, VT , VS0 , δ 0 , q0 , , $0 ), con V S 0 = VS ∪ {]}. Cada transici´on del EPDA 0 , Zm . . . Z1 , Zi0 . . . Z10 ) ∈ δ(q, a, Z) (q 0 , Zk0 . . . Zi+1

donde q, q 0 ∈ Q, a ∈ VT ∪ {}, Z, Z1 , . . . , Zm , Z10 , . . . , Zk ∈ VS y m ≤ 2, se transformar´a en las siguientes transiciones del 2–SA, para todo Z 00 ∈ VS : 0 . . . ) ∈ δ 0 (q, a, Z, Z 00 ) (q 0 , Zm . . . Z1 Zi0 . . . Z10 , Z 00 ]Zk0 . . . Zi+1

donde el n´ umero de separadores en ambas pilas es es el mismo y ] es un nuevo s´ımbolo de pila utilizado para separar las pilas unitarias que permanecen en espera en la segunda pila del 2–SA. Este tipo de transiciones no forman parte de las transiciones elementales que hemos propuesto para los aut´omatas con dos pilas puesto que se introduce m´as de un separador, pero pueden ser obtenidas mediante la aplicaci´on sucesiva de dichas transiciones [25] y son utilizadas aqu´ı para simplificar la prueba. Adicionalmente, para todo q ∈ Q deberemos a˜ nadir las transiciones (q, , ) ∈ δ(q, a, , ) que eliminan los separadores, las transiciones (q, Z2 , ) ∈ δ(q, , , Z2 ) que pasan elementos de la segunda pila a la primera para procesar aquellas pilas unitarias que hab´ıan sido dejadas en espera y las transiciones (q, , ) ∈ δ(q, , , ]) que finalizan el procesamiento de las pilas unitarias dejadas en espera.

2

Los aut´omatas con dos pilas que acabamos de definir presentan un inter´es meramente te´orico, puesto que la definici´on de esquemas de compilaci´on para LIG y TAG dista de ser simple y porque no ha sido posible dise˜ nar hasta el momento una t´ecnica de tabulaci´on que permite su ejecuci´on en tiempo polinomial.

10.3.

Aut´ omatas con dos pilas fuertemente dirigidos

Puesto que los aut´omatas con dos pilas presentados en la secci´on precedente no son satisfactorios, procederemos a su redefinici´on. Los objetivos de la misma son, por una parte, permitir la descripci´on de forma simple de esquemas de compilaci´on para LIG y TAG, y por otra parte posibilitar el desarrollo de una t´ecnica de tabulaci´on que permita ejecutar dichos aut´omatas en tiempo polinomial. Seguiremos suponiendo que dichos aut´omatas constan de dos pilas, una de las cuales recibir´a el nombre de pila maestra (master stack, MS) mientras que la otra se denominar´a pila auxiliar (auxiliary stack, AS). En ambas pilas se almacenar´an elementos de un alfabeto de pila y separadores. Denominaremos sesi´ on a la parte de cada pila comprendida entre dos de dichos separadores. El n´ umero de sesiones debe ser el mismo en ambas pilas. Prescindiremos del control de estado finito, tal y como hemos hecho anteriormente en el caso de los aut´omatas a pila (cap´ıtulo 5) y los aut´omatas a pila embebidos (cap´ıtulos 6 y 7). 1

Tilman Becker, comunicaci´ on personal, 1996.

10.3 Aut´ omatas con dos pilas fuertemente dirigidos

337

Si no se establece ninguna restricci´on, las dos pilas del aut´omata pueden ser utilizadas combinadamente para emular una m´aquina de Turing [85]. Con el fin de limitar la potencia expresiva a la clase de los lenguajes de adjunci´on de a´rboles, restringiremos las operaciones permitidas en cada pila en funci´on de los dos modos siguientes de trabajo: Un modo de escritura w en el cual no se permite extraer elementos de la pila maestra. Un modo de borrado e en el cual no se permite apilar elementos en la pila maestra. En caso de creaci´on de una nueva sesi´on, el aut´omata pasa a modo de escritura. Las sesiones de ambas pilas podr´an ser eliminadas simult´aneamente (mediante el borrado de los separadores en ambas pilas) u ´nicamente en modo de borrado y cuando la sesi´on de la pila auxiliar est´e vac´ıa. Cuando se eliminan sesiones, el aut´omata pasar´a al modo en que se encontraba antes de crear dichas sesiones. Por convenci´on, definimos una relaci´on de orden entre modos, de tal modo que se cumple que w < e. Para posibilitar el dise˜ no de una t´ecnica de tabulaci´on, estableceremos una restricci´on adicional seg´ un la cual en los modos w y e en cada sesi´on de la pila auxiliar se aplicar´an las mismas operaciones de apilamiento y extracci´on, pero en orden inverso. Para ello, cada transici´on de apilamiento en la pila maestra escribir´a una marca de acci´on que indique la operaci´on realizada sobre la pila auxiliar: % para indicar una operaci´on de apilamiento. → para indicar que no se ha realizado modificaci´on alguna sobre una pila auxiliar. & para indicar que se ha extra´ıdo el elemento en la cima de la pila auxiliar. Las dos marcas de acci´on siguientes realizar´an el papel de separadores de sesiones: |=w indica la creaci´on de una nueva sesi´on a partir de una configuraci´on en modo de escritura. |=e indica la creaci´on de una nueva sesi´on a partir de una configuraci´on en modo de borrado. Las marcas de acci´on dirigir´an, durante el modo de borrado, las operaciones que se pueden realizar sobre la pila auxiliar cuando se aplica una transici´on POP sobre la pila maestra. Puesto que las transiciones de apilamiento sobre la pila maestra escriben las marcas en el modo w, denominaremos ⊗WRITE a dichas transiciones. Las transiciones POP de la pila maestra son las encargadas de borrar las marcas en el modo e, por lo que recibir´an el nombre de transiciones ⊗ERASE, donde ⊗ ∈ {|=w , |=e , %, →, &}. Una configuraci´on (m, Ξ, ξ, w) del aut´omata vendr´a determinada por el modo m en que se encuentre, el contenido Ξ de la pila maestra, el contenido ξ de la pila auxiliar y la parte w de la cadena de entrada que resta por leer. En la nueva versi´on que acabamos de describir de los aut´omatas con dos pilas, los movimientos que se pueden realizar en un momento dado est´an restringidos en gran medida por movimientos realizados en alg´ un momento anterior. Es por ello que recibir´an el nombre de aut´ omatas con dos pilas fuertemente dirigidos (Strongly-Driven 2–Stack Automata, SD–2SA). Formalmente, definiremos un aut´omata con dos pilas fuertemente dirigido como una tupla (VT , VS , $0 , $f , VI , D, Θ), donde: VT es un conjunto finito de s´ımbolos terminales. VS es un conjunto finito de s´ımbolos de la pila maestra.

338

Aut´ omatas con dos pilas $0 ∈ VS es el s´ımbolo inicial de la pila maestra. $f ∈ VS es el s´ımbolo final de la pila maestra. VI es un conjunto finito de s´ımbolos de la pila auxiliar. D = {|=w , |=e , %, →, &} es el conjunto de marcas de acci´on. Θ es un conjunto finito de transiciones de los siguientes tipos: a

SWAP1 : Transiciones de la forma (m, C, ) 7−→ (m, F, ), donde m ∈ {w, e}, C, F ∈ VS y a ∈ VT ∪ . El resultado de aplicar una transici´on de este tipo a una configuraci´on (m, ΞC, ξ, aw) es una configuraci´on (m, ΞF, ξ, w). a

SWAP2 : Transiciones de la forma (w, C, |=m ) 7−→ (e, F, |=m ). El resultado de aplicar una transici´on este tipo a una configuraci´on (m, ΞC, ξ|=m , aw) es una configuraci´on (m, ΞF, ξ|=m , w). Estas transiciones son las u ´nicas que permiten pasar del modo de escritura al modo de borrado. |=WRITE : Transiciones de la forma (m, C, ) 7−→ (w, C|=m F, |=m ) que al ser aplicadas a una configuraci´on (m, ΞC, ξ, w) producen una configuraci´on (w, ΞC|=m F, ξ|=m ). →WRITE Transiciones de la forma (w, C, ) 7−→ (w, C→F, ) que al ser aplicadas a una transici´on (w, ΞC, ξ, w) producen una configuraci´on (w, ΞC→F, ξ, w). %WRITE Transiciones de la forma (w, C, ) 7−→ (w, C%F, γ 0 ) que al ser aplicadas a una transici´on (w, ΞC, ξ, w) producen una configuraci´on (w, ΞC%F, ξγ 0 , w). &WRITE Transiciones de la forma (w, C, γ) 7−→ (w, C&F, ) que al ser aplicadas a una transici´on (w, ΞC, ξγ, w) producen una configuraci´on (w, ΞC&F, ξ, w). |=ERASE : Transiciones de la forma (e, C|=m F, |=m ) 7−→ (m, G, ) que al ser aplicadas a una configuraci´on (m, ΞC|=m F, ξ|=m , w) producen una configuraci´on (m, ΞG, ξ, w). →ERASE : Transiciones de la forma (e, C→F, ) 7−→ (e, G, ) que al ser aplicadas a una configuraci´on (e, ΞC→F, ξ, w) producen una configuraci´on (e, ΞG, ξ, w). %ERASE : Transiciones de la forma (e, C%F, η 0 ) 7−→ (e, G, ) que al ser aplicadas a una configuraci´on (e, ΞC%F, ξη 0 , w) producen una configuraci´on (e, ΞG, ξ, w). &ERASE : Transiciones de la forma (e, C&F, ) 7−→ (e, G, η) que al ser aplicadas a una configuraci´on (e, ΞC→F, ξ, w) producen una configuraci´on (e, ΞG, ξη, w). Una configuraci´ on de un aut´omata con dos pilas fuertemente dirigido es una tupla (m, Ξ, ξ, w), donde m ∈ {w, e}, Ξ ∈ (DVS )∗ , ξ ∈ (DVI∗ )∗ y w ∈ VT∗ . Una configuraci´on (m, Ξ, ξ, aw) deriva una configuraci´on (m0 , Ξ0 , ξ 0 , w), denotado mediante (m, Ξ, ξ, aw) ` (m0 , Ξ, ξ, w), si y s´olo si existe una transici´on que aplicada en modo m transforma la pila maestra Ξ en Ξ0 y la pila auxiliar ξ en ξ 0 al tiempo que lee a ∈ VT ∪ {} de la cadena de entrada, mientras el aut´omata pasa a modo m0 . En caso de ser necesario identificar una derivaci´on ∗

d concreta, utilizaremos la notaci´on `d . Denotamos por ` el cierre reflexivo y transitivo de `. Decimos que una cadena de entrada w es aceptada por un aut´omata con dos pilas fuertemente dirigido si ∗ (w, |=w $ , |=w , w) ` (e, |=w $ |=w $ , |=w |=w , ) 0

0

f

El lenguaje aceptado por un aut´omata con dos pilas fuertemente dirigido es el conjunto ∗ {w ∈ VT∗ | (w, |=w $0 , |=w , w) ` (e, |=w $0 |=w $f , |=w |=w , )}

10.3 Aut´ omatas con dos pilas fuertemente dirigidos

339

Ejemplo 10.1 El aut´omata con dos pilas fuertemente dirigido de la tabla 10.1 acepta el lenguaje {an bn cn dn | n > 0}. En la tabla 10.2 se muestra la derivaci´on para la cadena de entrada aaabbbcccddd en dicho aut´omata. La primera columna indica la transici´on aplicada, la segunda se˜ nala el modo del aut´omata en ese momento, la tercera muestra el contenido de la pila maestra, la cuarta muestra el contenido de la pila auxiliar y la quinta muestra la parte de la cadena de entrada que resta por leer. ¶

10.3.1.

Esquemas de compilaci´ on de gram´ aticas lineales de ´ındices

Para la compilaci´on de las gram´aticas lineales de ´ındices en aut´omatas con dos pilas fuertemente dirigidos utilizaremos la pila maestra para almacenar no-terminales de la gram´atica y la pila auxiliar para almacenar los ´ındices. Cada sesi´on corresponder´a a una espina en la derivaci´on de la gram´atica con respecto a la cadena de entrada. Puesto que todos los no-terminales de una espina trabajan sobre la misma pila de ´ındices, en todo momento se cumplir´a que el contenido de una sesi´on de la pila auxiliar se corresponder´a con el valor de la pila de ´ındices asociada al no-terminal situado en la cima de la sesi´on correspondiente en la pila maestra. Podemos definir un esquema de compilaci´on gen´erico mediante la parametrizaci´on de la informaci´on predicha en la fase de llamada y la informaci´on propagada en la fase de retorno. Los par´ametros a considerar son: → − A , que se refiere a la predicci´on realizada sobre el no-terminal A durante la fase descendente de la estrategia de an´alisis. → − γ , que se refiere a la predicci´on realizada sobre el ´ındice γ. ← − A , que se refiere a la propagaci´on de informaci´on respecto al no-terminal A durante la fase ascendente de la estrategia de an´alisis. ← − γ , que se refiere a la propagaci´on de informaci´on respecto al ´ındice γ.

Esquema de compilaci´ on 10.1 El esquema de compilaci´on gen´erico de una gram´atica lineal de ´ındices en un aut´omata con dos pilas fuertemente dirigido queda definido por el conjunto de ← − reglas mostrado en la tabla 10.3 y por los elementos inicial $0 y final S . § El esquema de compilaci´on gen´erico se puede convertir en esquemas de compilaci´on que incorporan estrategias espec´ıficas. En la tabla 10.4 se muestran los valores que toman los diferentes par´ametros para las estrategias de an´alisis de LIG m´as comunes. En dicha tabla,  indica un s´ımbolo de pila especial que no aparece inicialmente en VS y 3 indica un elemento especial que no aparece inicialmente en VI .

10.3.2.

Esquemas de compilaci´ on de gram´ aticas de adjunci´ on de ´ arboles

Para la compilaci´on de gram´aticas de adjunci´on de a´rboles en aut´omatas con dos pilas fuertemente dirigidos haremos uso de la pila maestra para almacenar los nodos de los a´rboles elementales seg´ un se van visitando. La pila auxiliar se utilizar´a para almacenar la pila de adjunciones pendiente en cada nodo, de tal modo que los valores almacenados en una sesi´on de la pila auxiliar se corresponden con la pila de adjunciones pendientes del nodo situado en la cima de la sesi´on correspondiente en la pila maestra. Podemos definir un esquema de compilaci´on gen´erico mediante la parametrizaci´on del flujo de informaci´on de las fases de llamada y retorno. Los par´ametros a considerar son:

340

Aut´ omatas con dos pilas

(a) (b) (c)

(w, $0 , ) 7−→ (w, $0 |=w A, |=w ) a (w, A, ) 7−→ (w, A0 , ) (w, A0 , ) 7−→ (w, A0 %A, γ)

(d) (e)

(w, A0 , ) 7−→ (w, B 0 , ) (w, B 0 , γ) 7−→ (w, B 0 &B, )

(f ) (g) (h) (i)

(w, B, ) 7−→ (w, B 0 , ) c (w, B 0 , |=m ) 7−→ (e, C 0 , |=m ) (e, B 0 &C 0 , ) 7−→ (e, C, η) c (e, C, ) 7−→ (e, C 0 , )

(j) (k)

(e, C 0 , ) 7−→ (e, D 0 , ) (e, A0 %D0 ) 7−→ (e, D, )

b

b

d

d

(l) (e, D, ) 7−→ (e, D 0 , ) (m) (e, D 0 , ) 7−→ (e, $f , ) Tabla 10.1: Transiciones del SD–2SA que acepta {an bn cn dn | n > 0}

w (a) w (b) w (c) w (b) w (c) w (b) w (d) w (e) w (f ) w (e) w (f ) w (g) e (h) e (i) e (h) e (i) e (j) e (k) e (l) e (k) e (l) e (m) e

|=w $0 |=w $0 |=w $0 |=w $0 |=w $0 |=w $0 |=w $0 |=w $0 |=w $0 |=w $0 |=w $0 |=w $0 |=w $0 |=w $0 |=w $0 |=w $0 |=w $0 |=w $0 |=w $0 |=w $0 |=w $0 |=w $0 |=w $0

|=w A |=w A0 |=w A0 %A |=w A0 %A0 |=w A0 %A0 %A |=w A0 %A0 %A0 |=w A0 %A0 %B 0 |=w A0 %A0 %B 0 &B |=w A0 %A0 %B 0 &B 0 |=w A0 %A0 %B 0 &B 0 &B |=w A0 %A0 %B 0 &B 0 &B 0 |=w A0 %A0 %B 0 &B 0 &C 0 |=w A0 %A0 %B 0 &C |=w A0 %A0 %B 0 &C 0 |=w A0 %A0 %C |=w A0 %A0 %C 0 |=w A0 %A0 %D0 |=w A0 %D |=w A0 %D0 |=w D |=w D0 |=w $ f

|=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w

aaabbbcccddd aaabbbcccddd aabbbcccddd γ aabbbcccddd γ abbbcccddd γγ abbbcccddd γγ bbbcccddd γγ bbcccddd γ bbcccddd γ bcccddd bcccddd cccddd ccddd η ccddd η cddd ηη cddd ηη ddd ηη dd η dd η d d

Tabla 10.2: Configuraciones del SD–2SA para la cadena de entrada aaabbbcccddd

10.3 Aut´ omatas con dos pilas fuertemente dirigidos

[INIT]

(w, $0 , ) 7−→ (w, $0 |=w ∇0,0 , |=w )

[CALL]

−−−−→ (m, ∇r,s , ) 7−→ (w, ∇r,s |=m Ar,s+1 , |=m )

341

Ar,0 [◦◦γ] → Υ1 Ar,s+1 [ ]Υ2

−−−−→ [SCALL-1] (w, ∇r,s , ) 7−→ (w, ∇r,s →Ar,s+1 , )

Ar,0 [◦◦] → Υ1 Ar,s+1 [◦◦]Υ2

→ −−−−→ − [SCALL-2] (w, ∇r,s , ) 7−→ (w, ∇r,s %Ar,s+1 , γ 0 )

Ar,0 [◦◦] → Υ1 Ar,s+1 [◦◦γ 0 ]Υ2

−−−−→ − [SCALL-3] (w, ∇r,s , → γ ) 7−→ (w, ∇r,s &Ar,s+1 , )

Ar,0 [◦◦γ] → Υ1 Ar,s+1 [◦◦]Υ2

[SEL]

−−→ (w, Ar,0 , ) 7−→ (w, ∇r,0 , )

[PUB]

←−− (e, ∇r,nr , ) 7−→ (e, Ar,0 , )

[RET]

←−−−− (e, ∇r,s |=m Ar,s+1 , |=m ) 7−→ (m, ∇r,s+1 , )

Ar,0 [◦◦γ] → Υ1 Ar,s+1 [ ]Υ2

[SRET-1]

←−−−− (e, ∇r,s →Ar,s+1 , ) 7−→ (e, ∇r,s+1 , )

Ar,0 [◦◦] → Υ1 Ar,s+1 [◦◦]Υ2

[SRET-2]

− ←−−−− ← (e, ∇r,s %Ar,s+1 , γ 0 ) 7−→ (e, ∇r,s+1 , )

Ar,0 [◦◦] → Υ1 Ar,s+1 [◦◦γ 0 ]Υ2

[SRET-3]

←−−−− − (e, ∇r,s &Ar,s+1 , ) 7−→ (e, ∇r,s+1 , ← γ)

Ar,0 [◦◦γ] → Υ1 Ar,s+1 [◦◦]Υ2

[SCAN]

−−→ ←−− a (w, Ar,0 , |=m ) 7−→ (e, Ar,0 , |=m )

Ar,0 [ ] → a

r 6= 0

Tabla 10.3: Reglas del esquema de compilaci´on gen´erico de LIG en SD–2SA

−−−−→ Ar,s+1

→ − γ

←−−−− Ar,s+1

← − γ



3

Ar,s+1

γ

Ar,s+1

3

Ar,s+1

γ

Descendente

Ar,s+1

3



γ

Ascendente



γ

Ar,s+1

γ

Ar,s+1

γ

Ar,s+1

γ

Descendente

Ar,s+1

γ



γ

Ascendente



γ

Ar,s+1

3

Ar,s+1

γ

Ar,s+1

3

Ar,s+1

γ



3

estrategia-CF

estrategia-´ındices

Ascendente Earley

Earley

Earley Descendente

ascendente

Earley

descendente

Tabla 10.4: Par´ametros del esquema de compilaci´on gen´erico de LIG en SD–2SA

342

Aut´ omatas con dos pilas −−→ γ γ Nr,s , la informaci´on predicha acerca del nodo Nr,s . ←−γ− γ Nr,s , la informaci´on propagada acerca del nodo Nr,s .

Esquema de compilaci´ on 10.2 El esquema de compilaci´on gen´erico de una gram´atica de adjunci´on de a´rboles en un aut´omata con dos pilas fuertemente dirigido queda definido por el ←− conjunto de reglas mostrado en la tabla 10.5 y los elementos inicial $ 0 y final >α , con α ∈ I. En este esquema de an´alisis sint´actico el cambio de modo de escritura a modo de borrado se produce, adem´as de en las transiciones producidas por la regla de compilaci´on [SCAN], en las transiciones producidas por la regla de compilaci´on [PUB2]. Ello se debe a que en las producciones de los a´rboles iniciales no son aplicables las reglas [SCALL] y [SRET], por lo cual todo cambio de modo realizado por una regla [SCAN] es eliminado por una regla [RET]. § El esquema de compilaci´on gen´erico puede convertirse en esquemas de compilaci´on para diferentes estrategias de an´alisis seg´ un los valores que tomen los par´ametros con respecto a su ubicaci´on en las pilas maestra y auxiliar, tal y como se indica en la tabla 10.6.

10.3.3.

SD–2SA y los lenguajes de adjunci´ on de ´ arboles

Los lenguajes aceptados por los aut´omatas con dos pilas fuertemente dirigidos coinciden con los lenguajes de adjunci´on de a´rboles. Para demostrar esta aseveraci´on definiremos y demostraremos los dos teoremas siguientes. Teorema 10.3 Los lenguajes adjunci´ on de a ´rboles son un subconjunto de los lenguajes aceptados por la clase de los aut´ omatas con dos pilas fuertemente dirigidos. Demostraci´on: Por el esquema de compilaci´on de TAG en SD–2SA presentado anteriormente, a partir de cualquier gram´atica de adjunci´on de a´rboles es posible construir un SD–2SA que acepta el lenguaje reconocido por dicha gram´atica. An´alogamente, por el esquema de compilaci´on de LIG en SD–2SA, a partir de cualquier gram´atica lineal de ´ındices es posible construir un SD–2SA que acepta el lenguaje reconocido por dicha gram´atica. 2

Teorema 10.4 La clase de los lenguajes aceptados por los aut´ omatas con dos pilas fuertemente dirigidos es un subconjunto de los lenguajes de adjunci´ on de a ´rboles. Demostraci´on: Mostraremos que para todo SD–2SA existe una gram´atica lineal de ´ındices tal que el lenguaje reconocido por la gram´atica coincide con el lenguaje aceptado por el aut´omata. Sea A = (VT , VS , $0 , $f , VI , D, Θ) un aut´omata lineal de ´ındices fuertemente dirigido. Construiremos una gram´atica lineal de ´ındices L = (VT , VN , VI0 , S, P ). El conjunto VN de no-terminales estar´a formado por pares hE, Bi tal que A, B ∈ VSD , donde VSD = {E m | E ∈ VS , m ∈ D}. El conjunto VI0 estar´a formado por pares hγ, ηi tal que γ, η ∈ VI . Para que L reconozca el lenguaje aceptado por A el conjunto de producciones en P ha de construirse a partir de las transiciones en Θ de la siguiente manera:

10.3 Aut´ omatas con dos pilas fuertemente dirigidos

343

[INIT]

(w, $0 , ) 7−→ (w, $0 |=w ∇α0,0 , |=w )

α∈I

[CALL]

−−− → m γ− (m, ∇γr,s , ) 7−→ (w, ∇γr,s |=m Nr,s+1 , |= )

γ Nr,s+1 6∈ espina(γ), nil ∈ adj(Nr,s+1 )

[SCALL]

−−− → γ− (w, ∇γr,s , ) 7−→ (w, ∇γr,s →Nr,s+1 , )

γ Nr,s+1 ∈ espina(γ), nil ∈ adj(Nr,s+1 )

[SEL]

−−→ γ , ) 7−→ (w, ∇γr,0 , ) (w, Nr,0

r 6= 0

[PUB1]

←−γ− , ) (e, ∇γr,nr , ) 7−→ (e, Nr,0

[PUB2]

←−γ− m , |= ) (w, ∇γr,nr , |=m ) 7−→ (e, Nr,0

[RET]

←−γ−−− m γ (e, ∇γr,s |=m Nr,s+1 , |= ) 7−→ (m, ∇γr,s+1 , ) Nr,s+1 6∈ espina(γ), nil ∈ adj(Nr,s+1 )

[SRET]

←−γ−−− , ) 7−→ (e, ∇γr,s+1 , ) (e, ∇γr,s → Nr,s+1

[SCAN]

−−→ ←−γ− m a γ (w, Nr,0 , |=m ) 7−→ (e, Nr,0 , |= )

γ ∈ espina(γ), nil ∈ adj(Nr,s+1 ) Nr,s+1 γ Nr,0 []→a

−−→ −−− → γ− [ACALL] (w, ∇γr,s , ) 7−→ (w, ∇γr,s %>β , Nr,s+1 )

γ β ∈ adj(Nr,s+1 )

[ARET]

←− ←−γ−−− (e, ∇γr,s %>β , Nr,s+1 ) 7−→ (e, ∇γr,s+1 , )

γ β ∈ adj(Nr,s+1 )

[FCALL]

−−− → −−− → γ γ− β γ− = Fβ , β ∈ adj(Nr,s+1 ) , ) Nf,0 ) 7−→ (w, ∇βf,0 &Nr,s+1 (w, ∇βf,0 , Nr,s+1

[FRET]

←−γ−−− ←−γ−−− β γ (w, ∇βf,0 & Nr,s+1 , ) 7−→ (e, ∇βf,1 , Nr,s+1 ) Nf,0 = Fβ , β ∈ adj(Nt,s+1 )

Tabla 10.5: Reglas del esquema de compilaci´on gen´erico de TAG en SD–2SA Estrategia-CF

Estrategia-adjunci´ on

MS −−− → γ− Nr,s+1

AS −−− → γ− Nr,s+1

MS ←−γ−−− Nr,s+1

AS ←−γ−−− Nr,s+1



3

γ Nr,s+1

γ Nr,s+1

γ Nr,s+1

3

γ Nr,s+1

γ Nr,s+1

Descendente

γ Nr,s+1

3



γ Nr,s+1

Ascendente



γ Nr,s+1

γ Nr,s+1

γ Nr,s+1

γ Nr,s+1

γ Nr,s+1

γ Nr,s+1

γ Nr,s+1

Descendente

γ Nr,s+1

γ Nr,s+1



γ Nr,s+1

Ascendente



γ Nr,s+1

γ Nr,s+1

3

γ Nr,s+1

γ Nr,s+1

γ Nr,s+1

3

γ Nr,s+1

γ Nr,s+1



3

Ascendente Earley

Earley

Earley Descendente

ascendente

Earley

descendente

Tabla 10.6: Par´ametros del esquema de compilaci´on gen´erico de TAG en SD–2SA

344

Aut´ omatas con dos pilas a

0

Para toda transici´on (m, C, ) 7−→ (m, F, ) y para todo E m ∈ VSD tal que m0 ≤ m creamos una producci´on 0

0

hE m , F m i[◦◦] → hE m , C m i[◦◦] a Para toda transici´on (w, C, |=m ) 7−→ (e, F, |=m ) y para todo E w ∈ VSD creamos la producci´on hE w , F e i[ ] → hE w , C w i[ ] a a

Para todo par de transiciones (e, C|=m F, |=m ) 7−→ (m, G, ) y m 0 m m00 ∈ VSD tal que m00 ≤ m crea(m, C, ) 7−→ (w, C|= F , |= ), y para todo E mos una producci´on 00 00 hE m , Gm i[◦◦] → hE m , C m i[◦◦] hF 0w , F e i[ ] Para todo par de transiciones (e, C→F, ) 7−→ (e, G, ) y (w, C, ) 7−→ (w, C→F 0 , ), y para todo E w ∈ VSD creamos una producci´on hE w , Ge i[◦◦] → hE w , C w i[ ] hF 0w , F e i[◦◦] Para todo par de transiciones (e, C%F, η 0 ) 7−→ (e, G, ) y (w, C, ) 7−→ (w, C%F 0 , γ 0 ), y para todo E w ∈ VSD creamos una producci´on hE w , Ge i[◦◦] → hE w , C w i[ ] hF 0w , F e i[◦◦hγ 0 , η 0 i] Para todo par de transiciones (e, C&F, ) 7−→ (e, G, η) y (w, C, γ) 7−→ (w, C&F 0 , ), y para todo E w ∈ VSD creamos una producci´on hE w , Ge i[◦◦hγ, ηi] → hE w , C w i[ ] hF 0w , F e i[◦◦] Para todo E m ∈ VSD creamos una producci´on hE m , E m i[ ] →  Para toda transici´on (w, $0 , ) 7−→ (w, $0 |=m F, |=m ), donde F ∈ VS − {$0 }, creamos una producci´on w e w h$w 0 , $0 i[◦◦] → hF , $f i[◦◦] w Con respecto al axioma de la gram´atica, tenemos que S = h$w 0 , $0 i. Dividiremos la demostraci´on en tres casos, cada uno correspondiente a un tipo espec´ıfico de derivaci´on. Tratamos a continuaci´on cada uno de los casos por separado. ∗

Caso 1. Existe una derivaci´on en el aut´omata (w, E, ξ1 , w) ` (w, C, ξ1 , ) para alg´un ξ1 ∈ VI∗ , en la que s´olo se han aplicado transiciones de tipo SWAP1, si y s´olo si existe una ∗ derivaci´on en la gram´atica hE w , C w i[ ] ⇒ w. La demostraci´on se realiza por inducci´on. El caso base lo constituyen los dos casos siguientes: 0

Si (w, E, ξ1 , ) ` (w, E, ξ1 , ) entonces existe una producci´on hE w , E w i[ ] → , por lo ∗ que hE w , E w i[ ] ⇒ . 0

Si hE w , E w i[ ] →  entonces existe una derivaci´on (w, E, ξ1 , ) ` (w, E, ξ1 , ) en el aut´omata. Por hip´otesis de inducci´on suponemos que se cumple para toda derivaci´on de longitud inferior a s. El paso de inducci´on contempla los dos casos siguientes: s

Si (w, E, ξ1 , wa) ` (w, C, ξ1 , a) ` (w, F, ξ1 , ), entonces existe una producci´on hE w , F w i[◦◦] → hE w , C w i[◦◦] a, por hip´otesis de inducci´on tenemos que ∗ ∗ hE w , C w i[ ] ⇒ w, por lo que hE w , F w i[ ] ⇒ wa. s Si hE w , F w i[ ] ⇒ hE w , C w i[ ] a ⇒ wa, entonces existe una transici´on s

a

(w, C, ) 7−→ (w, F, ), por hip´otesis de inducci´on (w, E, ξ1 , w) ` (w, C, ξ1 , ) pas

ra alg´ un ξ1 y en consecuencia (w, E, ξ1 , wa) ` (w, F, ξ1 , ).

10.3 Aut´ omatas con dos pilas fuertemente dirigidos

345

Caso 2. Existe una derivacio ’on del aut´omata (w, Ξ E, ξ1 , w1 w2 )

∗

` (w, Ξ C, ξ1 , w2 ) ` (w, Ξ C|=w F 0 , ξ1 |=w , w2 ) ∗ ` (e, Ξ C|=w F, ξ |=w , ) 1

` (w, Ξ G, ξ1 , ) ∗ si y s´olo si hE w , Gw i[ ] ⇒ w1 w2 . La demostraci´on se obtiene directamente a partir del caso 1 y de la existencia de una producci´on hE w , Gw i[◦◦] → hE w , C w i[◦◦] hF 0w , F e i[ ].

Caso 3. El caso principal de esta demostraci´on establece que hE w , C e i[α] ⇒ w si y ∗

∗

s´olo si (w, E, ξ, w) ` (e, C, φ, ) y se cumple que ξ = γ1 γ2 . . . γp , φ = η1 η2 . . . ηp y α = hγ1 , η1 ihγ2 , η2 i . . . hγp , ηp i, esto es, ξ es la pila obtenida como resultado de la proyecci´ on del primer componente de los elementos almacenados en α mientras que φ es la pila obtenida como resultado de la proyecci´on del segundo componente de los elementos almacenados en la pila de ´ındices α. Tratamos a continuaci´on de demostrar cada una de las direcciones de la implicaci´on: ∗

Si una derivaci´on (w, E, ξ, w) ` (e, C, φ, ) es el resultado de aplicar la secuencia t1 , . . . , ts de transiciones en Θ, entonces existe una secuencia p1 , . . . , p0s de producciones ∗ en P tal que la derivaci´on hE w , C e i[α] ⇒ w resultado de aplicar p1 , . . . , p0s reconoce w. La demostraci´on se realiza por inducci´on en la longitud de la derivaci´on del aut´omata. El caso base lo constituye la derivaci´on (w, E, |=m , ) ` (e, C, |=m , ), para la que existe la producci´on hE w , C e i[ ] → hE w , E w i[ ] a y la producci´on hE w , E w i[ ] → , por lo ∗ que hE w , C e i[ ] ⇒ a. Por hip´otesis de inducci´on suponemos que la proposici´on se cumple para cualquier derivaci´on del aut´omata de longitud s. En tal caso, durante el paso de inducci´on verificamos que se cumple para cualquier posible derivaci´on de longitud mayor que s: s

• Si (w, E, ξ, wa) ` (e, C, φ, a) ` (e, F, φ, ), existe una producci´on hE w , F e i[◦◦] → hE w , C e i[◦◦] a, por hip´otesis de inducci´on se cumple que ∗ ∗ hE w , C e i[α] ⇒ w, y en consecuencia hE w , F e i[α] ⇒ wa. s

s

2 1 • Si (w, E, ξ, w1 w2 ) ` (e, C, φ, w2 ) ` (w, C|=e F 0 , φ|=e , w2 ) ` (e, C|=e F, φ|=e , ) ` (e, G, φ, ), existe una producci´on hE w , Ge i[◦◦] → hE w , C e i[◦◦] hF 0w , F e i[ ], por ∗ ∗ hip´otesis de inducci´on se cumple que hE w , C e i[α] ⇒ w1 y hF 0w , F e i[ ] ⇒ w2 , y ∗ en consecuencia hE w , Ge i[α] ⇒ w1 w2 .

s2

s1

• Si (w, E, ξ, w1 w2 ) ` (w, C, ξ, w2 ) ` (w, C→F 0 , φ, w2 ) ` (e, C→F, φ, ) ` (e, G, φ, ), existe una producci´on hE w , Ge i[◦◦] → hE w , C w i[ ] hF 0w , F e i[◦◦], ∗ ∗ por los casos 1 y 2 se cumple que hE w , C w i[ ] ⇒ w1 y hF 0w , F e i[ ] ⇒ w2 , y ∗ en consecuencia hE w , Ge i[α] ⇒ w w . 1

s1

2

s2

` ` (w, C, ξ, w2 ) ` (w, C%F 0 , φγ 0 , w2 ) • Si (w, E, ξ, w1 w2 ) 0 (e, C%F, φη , ) ` (e, G, φ, ), existe una producci´on hE w , Ge i[◦◦] → hE w , C w i[ ] hF 0w , F e i[◦◦hγ 0 , η 0 i], por los casos 1 y 2 se ∗ ∗ cumple que hE w , C w i[ ] ⇒ w1 y hF 0w , F e i[αhγ 0 , ηi] ⇒ w2 , y en consecuencia ∗ hE w , Ge i[α] ⇒ w1 w2 . s1

s2

` ` (w, C, ξ, w2 ) ` (w, C&F 0 , φ, w2 ) • Si (w, E, ξγ, w1 w2 ) (e, C&F, φ, ) ` (e, G, φη, ), existe una producci´on hE w , Ge i[◦◦hγ, ηi] → hE w , C w i[ ] hF 0w , F e i[◦◦], por los casos 1 y 2 se ∗ ∗ cumple que hE w , C w i[ ] ⇒ w1 y hF 0w , F e i[α] ⇒ w2 , y en consecuencia ∗ hE w , Ge i[αhγ 0 , ηi] ⇒ w1 w2 .

346

Aut´ omatas con dos pilas ∗ Si una derivaci´on izquierda hC w , E e i[α] ⇒ w reconoce la cadena w como resultado de aplicar la secuencia p1 , . . . , ps de producciones en P , entonces existe una secuencia de ∗

transiciones t1 , . . . , ts en Θ tal que la derivaci´on (w, C, ξ, w) ` (e, E, φ, ) es el resultado de aplicar la secuencia de transiciones t1 , . . . , ts . La demostraci´on se realiza por inducci´on en la longitud de las derivaciones de la gram´atica. El caso base de la demostraci´on lo constituye la derivaci´on hE w , C e i[ ] ⇒ hE w , E w i[ ] a ⇒ a, para la que existe una derivaci´on (w, E, |=m , a) ` (e, C, |=m , ) en el aut´omata. Por hip´otesis de inducci´on suponemos que la proposici´on se cumple para cualquier derivaci´on de la gram´atica de longitud s. En tal caso, durante el paso de inducci´on verificamos que se cumple para cualquier posible derivaci´on de longitud mayor que s: s a • Si hE w , F e i[α] ⇒ hE w , C e i[α] a ⇒ wa), existe una transici´on (e, C, ) 7−→ ∗

(e, F, ), por hip´otesis de inducci´on se cumple que (w, E, ξ, w) ` (e, C, φ, ) y por ∗

consiguiente (w, E, ξ, wa) ` (e, F, φ, ). s1 s2 • Si hE w , Ge i[α] ⇒ hE w , C e i[α] hF 0w , F e i[ ] ⇒ w1 hF 0w , F e i[ ] ⇒ w1 w2 , e 0 e existe una transici´on (e, C, ) 7−→ (w, C|= F , |= ) y una transici´on (C|=e F, |=e ) 7−→ (e, G, ), por hip´otesis de inducci´on se cumple que ∗ ∗ (w, E, ξ, w ) ` (e, C, φ, ) y que (w, F 0 , |=e , w ) ` (e, F, |=e , ) y en conse1

2

∗

∗

cuencia se cumple que (w, E, ξ, w1 w2 ) ` (e, C, φ, w2 ) ` (w, C|=e F 0 , φ|=e , w2 ) ` (e, C|=e F, φ|=e , ) ` (e, G, φ, ). s1 s2 • Si hE w , Ge i[α] ⇒ hE w , C w i[ ] hF 0w , F e i[α] ⇒ w1 hF 0w , F e i[α] ⇒ w1 w2 , 0 existe una transici´on (w, C, ) 7−→ (w, C→F , ) y una transici´on ∗

(e, C→F, ) 7−→ (e, G, ), por los casos 1 y 2 se cumple que (w, E, ξ, w1 ) ` ∗

(w, C, ξ, ) y por hip´otesis de inducci´on (w, F 0 , ξ, w2 ) ` (e, F, φ, ) y en con∗

∗

secuencia se cumple que (w, E, ξ, w1 w2 ) ` (w, C, ξ, w2 ) ` (w, C→F 0 , ξ, w2 ) ` (e, C→F, φ, ) ` (e, G, φ, ). s2 s1 w1 hF 0w , F e i[αhγ 0 , η 0 i] ⇒ • Si hE w , Ge i[α] ⇒ hE w , C w i[ ] hF 0w , F e i[αhγ 0 , η 0 i] ⇒ w1 w2 , existe una transici´on (w, C, ) 7−→ (C%F 0 , γ 0 ) y una transici´on ∗

(e, C%F, η 0 ) 7−→ (e, G, ), por los casos 1 y 2 se cumple que (w, E, ξ, w1 ) ` ∗

(w, C, ξ, ) y por hip´otesis de inducci´on (w, F 0 , ξγ 0 , w2 ) ` (e, F, φη 0 , ) y en con∗

∗

secuencia se cumple que (w, E, ξ, w1 w2 ) ` (w, C, ξ, w2 ) ` (w, C%F 0 , ξγ 0 , w2 ) ` (e, C%F, φη 0 , ) ` (e, G, φ, ). s2 s1 w1 w2 , w1 hF 0w , F e i[α] ⇒ • Si hE w , Ge i[αhγ, ηi] ⇒ hE w , C w i[ ] hF 0w , F e i[α] ⇒ 0 existe una transici´on (w, C, γ) 7−→ (C&F , ) y una transici´on ∗

(e, C&F, ) 7−→ (e, G, η), por los casos 1 y 2 se cumple que (w, E, ξγ, w1 ) ` ∗

(w, C, ξγ, ) y por hip´otesis de inducci´on (w, F 0 , ξ, w2 ) ` (e, F, φ, ) y en conse∗

∗

cuencia se cumple que (w, E, ξγ, w1 w2 ) ` (w, C, ξγ, w2 ) ` (w, C&F 0 , ξ, w2 ) ` (e, C&F, φ, ) ` (e, G, φη, ).

2

10.3.4.

Tabulaci´ on

A partir de las caracter´ısticas propias de los aut´omatas con dos pilas fuertemente dirigidos, podemos observar que toda derivaci´on puede clasificarse en uno de los tipos que se enuncian a continuaci´on.

10.3 Aut´ omatas con dos pilas fuertemente dirigidos

347

Derivaciones de llamada. Son aquellas que se inician y terminan en modo de escritura en la misma sesi´on. Presentan alguna de las siguientes formas, dependiendo de la u ´ltima transici´on aplicada: ∗

(w, ΞA, ξ, ah . . . an ) `d1 (w, ΞA Ξ1 B, ξγγ 0 , ai . . . an ) ∗

`d2 (w, ΞA Ξ1 B&C, ξγ, aj . . . an ) ∗

(w, ΞA, ξ, ah . . . an ) `d1 (w, ΞA Ξ1 B, ξγ, ai . . . an ) ∗

`d2 (w, ΞA Ξ1 B→C, ξγ, aj . . . an ) 0

(w, ΞB, ξγ 0 , ai . . . an ) `d1 (w, ΞB, ξγ 0 , ai . . . an ) ∗

`d2 (w, ΞB%C, ξγ 0 γ, aj . . . an ) donde γ, γ 0 ∈ VI (en el tercer caso γ 0 ∈ VI ∪{|=w , |=e }) y tanto A como B y C pertenecen a la misma sesi´on. A efectos de uniformizar las explicaciones que siguen, en las derivaciones de la u ´ltima forma identificaremos ΞA con ΞB y h con i. La subderivaci´on d 1 puede consultar A pero no puede alterar ese elemento de la pila maestra ni ninguno que quede por debajo. En d1 tambi´en se permite la consulta de γ 0 aunque no su modificaci´on ni la de ξ. La subderivaci´on d2 puede consultar B pero no puede alterar ni B ni los elementos de la pila maestra que quedan por debajo. Esta subderivaci´on tampoco puede modificar aquella parte de la pila auxiliar que finalmente queda por debajo de γ. En la figura 10.1 se muestra una representaci´on gr´afica de este tipo de derivaciones. umero de sesiones en Para cualquier Ξ0 ∈ (DVS )∗ y ξ 0 ∈ (|=x VI∗ )∗ tal que x ∈ {w, e} y el n´ Ξ0 y ξ 0 coincide, se cumple ∗

(w, Ξ0 A, ξ 0 , ah . . . an ) `d1 (w, Ξ0 A Ξ1 B, ξ 0 γγ 0 , ai . . . an ) ∗

`d2 (w, Ξ0 A Ξ1 B&C, ξ 0 γ, aj . . . an ) ∗

(w, Ξ0 A, ξ 0 , ah . . . an ) `d1 (w, Ξ0 A Ξ1 B, ξ 0 γ, ai . . . an ) ∗

`d2 (w, Ξ0 A Ξ1 B→C, ξ 0 γ, aj . . . an ) 0

(w, Ξ0 B, ξ 0 γ 0 , ai . . . an ) `d1 (w, Ξ0 B, ξ 0 γ 0 , ai . . . an ) ∗

`d2 (w, Ξ0 B%C, ξ 0 γ 0 γ, aj . . . an ) por lo que este tipo de derivaciones puede ser representado de manera compacta por los correspondientes ´ıtems de la forma [A, h | B, i, γ 0 , &C, j, γ | −, −, −, −, −]w [A, h | B, i, γ, →C, j, γ | −, −, −, −, −]w [B, i | B, i, γ 0 , %C, j, γ | −, −, −, −, −]w Derivaciones de retorno. Son aquellas que se inician en una sesi´on en modo de escritura y terminan en la misma sesi´on en modo de borrado. Estas derivaciones pueden ser de alguna de las tres formas siguientes: ∗

(w, ΞA, ξ, ah . . . an ) `d1 (w, ΞA Ξ1 B, ξγγ 0 , ai . . . an ) ∗

`d2 (w, ΞA Ξ1 B Ξ2 D, ξγ, ap . . . an ) ∗

`d3 (e, ΞA Ξ1 B Ξ2 D&E, φ, aq . . . an ) ∗

`d4 (e, ΞA Ξ1 B&C, φη, aj . . . an )

348

Aut´ omatas con dos pilas

γ

w C w B

γ γ

ξ

B

ξ

w A

ξ

A

A

h

i

j

γ

w C γ

w B

w A

ξ

ξ

A

h

A i

w

ξ

B

j

γ

B

w C

γ γ

B

ξ

ξ i

j

Figura 10.1: Derivaciones de llamada en SD–2SA

10.3 Aut´ omatas con dos pilas fuertemente dirigidos

349

∗

(w, ΞA, ξ, ah . . . an ) `d1 (w, ΞA Ξ1 B, ξγ, ai . . . an ) ∗

`d2 (w, ΞA Ξ1 B Ξ2 D, ξγ, ap . . . an ) ∗

`d3 (e, ΞA Ξ1 B Ξ2 D&E, φ, aq . . . an ) ∗

`d4 (e, ΞA Ξ1 B→C, φη, aj . . . an ) 0

(w, ΞB, ξγ 0 , ai . . . an ) `d1 (w, ΞB, ξγ 0 , ai . . . an ) ∗

`d2 (w, ΞB Ξ2 D, ξγ 0 γ, ap . . . an ) ∗

`d3 (e, ΞB Ξ2 D&E, φη 0 , aq . . . an ) ∗

`d4 (e, ΞB%C, φη 0 η, aj . . . an ) donde γ, γ 0 , γ 00 , η, η 0 ∈ VI (en el tercer caso γ 0 ∈ VI ∪ {|=w , |=e }) y tanto A como B, D, E y C pertenecen a la misma sesi´on. A efectos de uniformizar las explicaciones que siguen, en las derivaciones de la u ´ltima forma identificaremos ΞA con ΞB y h con i. La subderivaci´on d1 puede consultar A pero no puede alterar ese elemento de la pila maestra ni ninguno que quede por debajo. En d1 tambi´en se permite la consulta de γ 0 aunque no su modificaci´on ni la de ξ. Las subderivaciones d2 y d4 no pueden modificar B ni ning´ un elemento de la pila maestra que queda por debajo, aunque la subderivaci´on d2 puede consultar el propio B. La subderivaci´on d3 puede consultar D pero no puede alterar dicho elemento ni ning´ un otro de la pila maestra que quede por debajo. Las distintas apariciones de las pilas ξγ, ξγ 0 , φ y φη 0 que aparecen a lo largo de la derivaci´on se refieren a la misma pila y no a pilas que eventualmente resulten con los mismos contenidos despu´es de apilar y extraer diversos elementos. En la figura 10.2 se muestra una representaci´on gr´afica de este tipo de derivaciones. Para cualquier Ξ0 ∈ (DVS )∗ y ξ 0 , φ0 ∈ (|=x VI∗ )∗ tal que x ∈ {w, e}, el n´ umero de sesiones en Ξ0 , ξ 0 y φ0 coincide y, seg´ un el caso, existe una derivaci´on ∗

(w, D, ξγ, ap . . . an ) ` (e, D&E, φ, aq . . . an ) ∗

(w, D, ξγ, ap . . . an ) ` (e, D&E, φ, aq . . . an ) ∗

(w, D, ξγ 0 γ, ap . . . an ) ` (e, D&E, φη 0 , aq . . . an ) se cumple que ∗

(w, Ξ0 A, ξ 0 , ah . . . an ) `d1 (w, Ξ0 A Ξ1 B, ξ 0 γγ 0 , ai . . . an ) ∗

`d2 (w, Ξ0 A Ξ1 B Ξ2 D, ξ 0 γ, ap . . . an ) ∗

`d3 (e, Ξ0 A Ξ1 B Ξ2 D&E, φ0 , aq . . . an ) ∗

`d4 (e, Ξ0 A Ξ1 B&C, φ0 η, aj . . . an ) ∗

(w, Ξ0 A, ξ 0 , ah . . . an ) `d1 (w, Ξ0 A Ξ1 B, ξ 0 γ, ai . . . an ) ∗

`d2 (w, Ξ0 A Ξ1 B Ξ2 D, ξ 0 γ, ap . . . an ) ∗

`d3 (e, Ξ0 A Ξ1 B Ξ2 D&E, φ0 , aq . . . an ) ∗

`d4 (e, Ξ0 A Ξ1 B→C, φ0 η, aj . . . an )

350

Aut´ omatas con dos pilas 0

(w, Ξ0 B, ξ 0 γ 0 , ai . . . an ) `d1 (w, Ξ0 B, ξ 0 γ 0 , ai . . . an ) ∗

`d2 (w, Ξ0 B Ξ2 D, ξ 0 γ 0 γ, ap . . . an ) ∗

`d3 (e, Ξ0 B Ξ2 D&E, φ0 η 0 , aq . . . an ) ∗

`d4 (e, Ξ0 B%C, φ0 η 0 η, aj . . . an ) Ello posibilita que las derivaciones de retorno puedan ser representadas por ´ıtems de la forma [A, h | B, i, γ 0 , &C, j, η | D, p, γ, E, q]e [A, h | B, i, γ, →C, j, η | D, p, γ, E, q]e [A, h | B, i, γ 0 , %C, j, η | D, p, γ, E, q]e Derivaciones de puntos especiales. Son aquellas derivaciones que involucran una sesi´on vac´ıa en la pila auxiliar, por lo que presentan la forma ∗

(m, ΞB, ξγ 0 , ai . . . an ) ` (m0 , ΞB|=m C, ξγ 0 |=m , aj . . . an ) ∗

(w, ΞB, ξ|=m γ, ai . . . an ) ` (m0 , ΞB&C, ξ|=m , aj . . . an ) ∗

(w, ΞB, ξ|=m , ai . . . an ) ` (m0 , ΞB→C, ξ|=m , aj . . . an ) donde w ≤ m0 , γ 0 ∈ VI ∪ {|=w , |=e } y γ ∈ VI . Las derivaciones de puntos especiales se muestran gr´aficamente en la figura 10.3. Para cualquier Ξ0 ∈ (DVS )∗ y ξ 0 ∈ (|=x VI∗ )∗ tal que x ∈ {w, e} y el n´ umero de sesiones en Ξ0 y ξ 0 coincide, se cumple ∗

(m, Ξ0 B, ξ 0 γ 0 , ai . . . an ) ` (m0 , Ξ0 B|=m C, ξ 0 γ 0 |=m , aj . . . an ) ∗

(w, Ξ0 B, ξ 0 |=m γ, ai . . . an ) ` (m0 , Ξ0 B&C, ξ 0 |=m , aj . . . an ) ∗

(w, Ξ0 B, ξ 0 |=m , ai . . . an ) ` (m0 , Ξ0 B→C, ξ 0 |=m , aj . . . an ) por lo que podemos utilizar ´ıtems de la siguientes formas para representar este tipo de derivaciones: [−, − | B, i, γ 0 , |=m C, j, |=m | −, −, −, −, −]m0 [−, − | B, i, γ, &C, j, |=m | −, −, −, −, −]m0 [−, − | B, i, |=m , →C, j, |=m | −, −, −, −, −]m0 Los ´ıtems se combinan mediante las reglas descritas en la tabla 10.7, a partir de un ´ıtem inicial [−, − | −, −, −, |=w $0 , 0, |=w | −, −, −, −, −]w La aceptaci´on de la cadena se entrada a1 . . . an se indica mediante la presencia de ´ıtems de la forma [−, − | $0 , 0, |=w , |=w $f , n, |=w | −, −, −, −, −]e Teorema 10.5 La manipulaci´ on de configuraciones mediante la aplicaci´ on de transiciones en los aut´ omatas con dos pilas fuertemente dirigidos es equivalente a la manipulaci´ on de ´ıtems mediante las reglas de combinaci´ on de la tabla 10.7.

10.3 Aut´ omatas con dos pilas fuertemente dirigidos

351

e E γ

w D

ξ

φ

D

η

e C w B

γ γ

B

B

B

A

A

A

φ

ξ

w A

ξ

A

h

p

i

q

j

e E γ

w D

ξ

φ

D

η

e C w B

γ

B

B

B

A

A

A

φ

ξ

w A

ξ

A

h

p

i

q

j

e E γ γ

w D

η φ

D

ξ

η η φ

e C w B

γ

B

B

B

ξ i

p

q

Figura 10.2: Derivaciones de retorno en SD–2SA

j

352

Aut´ omatas con dos pilas

[A, h | B, i, γ 0 , ⊗C, j, η | D, p, γ, E, q]m [A, h | B, i, γ 0 , ⊗F, k, η | D, p, γ, E, q]m

a

(m, C, ) 7−→ (m, F, ), k = j si a = , k = j + 1 si a ∈ VT

[A, h | B, i, γ 0 , ⊗C, j, η | D, p, γ, E, q]m (m, C, ) 7−→ (w, C|=m F, |=m ) [−, − | C, j, η, |=m F, j, |=m | −, −, −, −, −]w [A, h | B, i, γ 0 , ⊗C, j, γ | −, −, −, −, −]w (w, C, ) 7−→ (w, C→F, ) [A, h | C, j, γ, →F, j, γ | −, −, −, −, −]w [A, h | B, i, γ 00 , ⊗C, j, γ | −, −, −, −, −]w (w, C, ) 7−→ (w, C%F, γ 0 ) [C, j | C, j, γ, %F, j, γ 0 | −, −, −, −, −]w [A, h | B, i, γ 00 , ⊗1 C, j, γ | −, −, −, −, −]w [M, m | N, t, γ 000 , ⊗2 A, h, γ 0 | −, −, −, −, −]w [M, m | C, j, γ, &F, j, γ 0 | −, −, −, −, −]w [−, − | B, i, γ 0 , ⊗C, j, |=m | −, −, −, −, −]w [−, − | B, i, γ 0 , ⊗F, k, |=m | −, −, −, −, −]e

(w, C, γ) 7−→ (w, C&F, )

a

(w, C, |=m ) 7−→ (e, F, |=m ), k = j si a = , k = j + 1 si a ∈ VT

[−, − | C, j, η, |=m F, k, |=m | −, −, −, −, −]e [A, h | B, i, γ 0 , ⊗C, j, η | D, p, γ, E, q]m [A, h | B, i, γ 0 , ⊗G, k, η | D, p, γ, E, q]m [A, h | C, j, γ, →F, k, η | D, p, γ, E, q]e [A, h | B, i, γ 0 , ⊗C, j, γ | −, −, −, −, −]w [A, h | B, i, γ 0 , ⊗G, k, η | D, p, γ, E, q]e [C, j | C, j, γ, %F, k, η 0 | D, p, γ 0 , E, q]e [A, h | B, i, γ 00 , ⊗C, j, γ | −, −, −, −, −]w [A, h | D, p, γ 0 , &E, q, η | O, u, γ, P, v]e [A, h | B, i, γ 00 , ⊗G, k, η | O, u, γ, P, v]e [M, m | C, j, γ, &F, k, η 0 | D, p, γ 0 , E, q]e [A, h | B, i, γ 00 , ⊗1 C, j, γ | −, −, −, −, −]w [M, m | N, t, γ 000 , ⊗2 A, h, γ 0 | −, −, −, −, −]w [A, h | B, i, γ 00 , ⊗1 G, k, η | C, j, γ, &F, k]e

(e, C|=m F, |=m ) 7−→ (m, G, )

(e, C→F, ) 7−→ (e, G, )

(e, C%F, η 0 ) 7−→ (e, G, )

(e, C&F, ) 7−→ (e, G, η)

Tabla 10.7: Reglas de combinaci´on de ´ıtems en SD–2SA

10.3 Aut´ omatas con dos pilas fuertemente dirigidos

w m

γ

B

353

m

C m

γ ξ

B

ξ i

j

m’ w

γ m

B

m

C

ξ

B

ξ i

j

m’ w

m

B

m

C

ξ

B

ξ i

j

Figura 10.3: Derivaciones de puntos especiales en SD–2SA Demostraci´on: Mostraremos que para toda derivaci´on existe una regla de combinaci´on que produce un ´ıtem que representa de forma compacta dicha derivaci´on y que para toda regla de combinaci´on se corresponde con una derivaci´on v´alida del aut´omata. Para ello detallaremos todas las posibles derivaciones, junto con las reglas de combinaci´on de ´ıtems correspondientes, en la siguiente lista. a

Derivaciones que son el resultado de aplicar una transici´on (m, C, ) 7−→ (m, F, ) • a una derivaci´on de llamada, con las tres posibilidades siguientes, en las cuales k = j si a =  y k = j + 1 si a ∈ VT : (w, ΞA, ξ, ah . . . an )

∗

` (w, ΞA Ξ1 B, ξγγ 0 , ai . . . an ) ∗

` (w, ΞA Ξ1 B&C, ξγ, aj . . . an ) ` (w, ΞA Ξ1 B&F, ξγ, ak . . . an ) [A, h | B, i, γ 0 , &C, j, γ | −, −, −, −, −]w a (w, C, ) 7−→ (w, F, ) [A, h | B, i, γ 0 , &F, k, γ | −, −, −, −, −]w

(w, ΞA, ξ, ah . . . an )

∗

` (w, ΞA Ξ1 B, ξγ, ai . . . an ) ∗

` (w, ΞA Ξ1 B→C, ξγ, aj . . . an ) ` (w, ΞA Ξ1 B→F, ξγ, ak . . . an ) [A, h | B, i, γ, →C, j, γ | −, −, −, −, −]w a (w, C, ) 7−→ (w, F, ) [A, h | B, i, γ, →F, k, γ | −, −, −, −, −]w

354

Aut´ omatas con dos pilas

0

(w, ΞB, ξγ 0 , ai . . . an )

` (w, ΞB, ξγ 0 , ai . . . an ) ∗

` (w, ΞB%C, ξγ 0 γ, aj . . . an ) ` (w, ΞB%F, ξγ 0 γ, ak . . . an ) [B, i | B, i, γ 0 , %C, j, γ | −, −, −, −, −]w a (w, C, ) 7−→ (w, F, ) [B, i | B, i, γ 0 , %F, k, γ | −, −, −, −, −]w • a una derivaci´on de retorno, con las tres posibilidades siguientes, en las cuales k = j si a =  y k = j + 1 si a ∈ VT : (w, ΞA, ξ, ah . . . an )

∗

` (w, ΞA Ξ1 B, ξγγ 0 , ai . . . an ) ∗

` (w, ΞA Ξ1 B Ξ2 D, ξγ, ap . . . an ) ∗

` (e, ΞA Ξ1 B Ξ2 D&E, φ, aq . . . an ) ∗

` (e, ΞA Ξ1 B&C, φη, aj . . . an ) ` (e, ΞA Ξ1 B&F, φη, ak . . . an ) [A, h | B, i, γ 0 , &C, j, η | D, p, γ, E, q]e a (e, C, ) 7−→ (e, F, ) [A, h | B, i, γ 0 , &F, k, η | D, p, γ, E, q]e (w, ΞA, ξ, ah . . . an )

∗

` (w, ΞA Ξ1 B, ξγ, ai . . . an ) ∗

` (w, ΞA Ξ1 B Ξ2 D, ξγ, ap . . . an ) ∗

` (e, ΞA Ξ1 B Ξ2 D&E, φ, aq . . . an ) ∗

` (e, ΞA Ξ1 B→C, φη, aj . . . an ) ` (e, ΞA Ξ1 B→F, φη, ak . . . an ) [A, h | B, i, γ, →C, j, η | D, p, γ, E, q]e a (e, C, ) 7−→ (e, F, ) [A, h | B, i, γ, →F, k, η | D, p, γ, E, q]e (w, ΞB, ξγ 0 , ai . . . an )

0

` (w, ΞB, ξγ 0 , ai . . . an ) ∗

` (w, ΞB Ξ2 D, ξγ 0 γ, ap . . . an ) ∗

` (e, ΞB Ξ2 D&E, φη 0 , aq . . . an ) ∗

` (e, ΞB%C, φη 0 η, aj . . . an ) ` (e, ΞB%F, φη 0 η, ak . . . an ) [B, i | B, i, γ 0 , %C, j, η | D, p, γ, E, q]e a (e, C, ) 7−→ (e, F, ) 0 [B, i | B, i, γ , %F, k, η | D, p, γ, E, q]e • a una derivaci´on de puntos especiales, con las tres posibilidades siguientes, en las cuales k = j si a =  y k = j + 1 si a ∈ VT : (m, ΞB, ξγ 0 , ai . . . an )

∗

` (m0 , ΞB|=m C, ξγ 0 |=m , aj . . . an ) ` (m0 , ΞB|=m F, ξγ 0 |=m , ak . . . an )

[−, − | B, i, γ 0 , |=m C, j, |=m | −, −, −, −, −]m0 a (w, C, ) 7−→ (w, F, ) [−, − | B, i, γ 0 , |=m F, k, |=m | −, −, −, −, −]m0 (w, ΞB, ξ|=m γ, ai . . . an )

∗

` (m0 , ΞB&C, ξ|=m , aj . . . an ) ` (m0 , ΞB&F, ξ|=m , ak . . . an )

10.3 Aut´ omatas con dos pilas fuertemente dirigidos

355

[−, − | B, i, γ, &C, j, |=m | −, −, −, −, −]m0 a (m0 , C, ) 7−→ (m0 , F, ) [−, − | B, i, γ, &F, k, |=m | −, −, −, −, −]m0 (w, ΞB, ξ|=m , ai . . . an )

∗

` (m0 , ΞB→C, ξ|=m , aj . . . an ) ` (m0 , ΞB→F, ξ|=m , ak . . . an )

[−, − | B, i, |=m , →C, j, |=m | −, −, −, −, −]m0 a (m0 , C, ) 7−→ (m0 , F, ) [−, − | B, i, |=m , →F, k, |=m | −, −, −, −, −]m0 Derivaciones que son el (m, C, ) 7−→ (w, C|=m F, |=m )

resultado

de

aplicar

una

transici´on

• a una derivaci´on de llamada, con las tres posibilidades siguientes: (w, ΞA, ξ, ah . . . an )

∗

` (w, ΞA Ξ1 B, ξγγ 0 , ai . . . an ) ∗

` (w, ΞA Ξ1 B&C, ξγ, aj . . . an ) ` (w, ΞA Ξ1 B&C|=w F, ξγ|=w , aj . . . an ) [A, h | B, i, γ 0 , &C, j, γ | −, −, −, −, −]w (w, C, ) 7−→ (w, C|=w F, |=w ) [−, − | C, j, γ, |=w F, j, |=w | −, −, −, −, −]w (w, ΞA, ξ, ah . . . an )

∗

` (w, ΞA Ξ1 B, ξγ, ai . . . an ) ∗

` (w, ΞA Ξ1 B→C, ξγ, aj . . . an ) ` (w, ΞA Ξ1 B→C|=w F, ξγ|=w , aj . . . an ) [A, h | B, i, γ, &C, j, γ | −, −, −, −, −]w (w, C, ) 7−→ (w, C|=w F, |=w ) [−, − | C, j, γ, |=w F, j, |=w | −, −, −, −, −]w 0

(w, ΞB, ξγ 0 , ai . . . an )

` (w, ΞB, ξγ 0 , ai . . . an ) ∗

` (w, ΞB%C, ξγ 0 γ, aj . . . an ) ` (w, ΞB%C|=w F, ξγ 0 γ|=w , aj . . . an ) [B, i | B, i, γ 0 , &C, j, γ | −, −, −, −, −]w (w, C, ) 7−→ (w, C|=w F, |=w ) [−, − | C, j, γ, |=w F, j, |=w | −, −, −, −, −]w • a una derivaci´on de retorno, con las tres posibilidades siguientes: (w, ΞA, ξ, ah . . . an )

∗

` (w, ΞA Ξ1 B, ξγγ 0 , ai . . . an ) ∗

` (w, ΞA Ξ1 B Ξ2 D, ξγ, ap . . . an ) ∗

` (e, ΞA Ξ1 B Ξ2 D&E, φ, aq . . . an ) ∗

` (e, ΞA Ξ1 B&C, φη, aj . . . an ) ` (w, ΞA Ξ1 B&C|=e F, φη|=e , aj . . . an ) [A, h | B, i, γ 0 , &C, j, η | D, p, γ, E, q]e (e, C, ) 7−→ (w, C|=e F, |=e ) [−, − | C, j, η, |=e F, j, |=e | −, −, −, −, −]w (w, ΞA, ξ, ah . . . an )

∗

` (w, ΞA Ξ1 B, ξγ, ai . . . an ) ∗

` (w, ΞA Ξ1 B Ξ2 D, ξγ, ap . . . an ) ∗

` (e, ΞA Ξ1 B Ξ2 D&E, φ, aq . . . an ) ∗

` (e, ΞA Ξ1 B→C, φη, aj . . . an ) ` (w, ΞA Ξ1 B→C|=e F, φη|=e , aj . . . an )

356

Aut´ omatas con dos pilas [A, h | B, i, γ, →C, j, η | D, p, γ, E, q]e (e, C, ) 7−→ (w, C|=e F, |=e ) [−, − | C, j, η, |=e F, j, |=e | −, −, −, −, −]w 0

(w, ΞB, ξγ 0 , ai . . . an )

` (w, ΞB, ξγ 0 , ai . . . an ) ∗

` (w, ΞB Ξ2 D, ξγ 0 γ, ap . . . an ) ∗

` (e, ΞB Ξ2 D&E, φη 0 , aq . . . an ) ∗

` (e, ΞB%C, φη 0 η, aj . . . an ) ` (w, ΞB%C|=e F, φη 0 η|=e , aj . . . an ) [B, i | B, i, γ 0 , %C, j, η | D, p, γ, E, q]e (e, C, ) 7−→ (w, C|=e F, |=e ) [−, − | C, j, η, |=e F, j, |=e | −, −, −, −, −]w • a una derivaci´on de puntos especiales, con las tres posibilidades siguientes: (m, ΞB, ξγ 0 , ai . . . an )

∗

` (m0 , ΞB|=m C, ξγ 0 |=m , aj . . . an ) 0 0 ` (w, ΞB|=m C|=m F, ξγ 0 |=m |=m , aj . . . an )

0 0 [−, − | B, i, γ 0 , |=m C, j, |=m | −, −, −, −, −]m0 (m0 , C, ) 7−→ (w, C|=m F, |=m ) [−, − | C, j, |=m , |=m0 F, j, |=m0 | −, −, −, −, −]w

∗

` (m0 , ΞB&C, ξ|=m , aj . . . an ) 0 0 ` (w, ΞB&C|=m F, ξ|=m |=m , aj . . . an )

(w, ΞB, ξ|=m γ, ai . . . an )

0 0 [−, − | B, i, γ, &C, j, |=m | −, −, −, −, −]m0 (m0 , C, ) 7−→ (w, C|=m F, |=m ) [−, − | C, j, |=m , |=m0 F, j, |=m0 | −, −, −, −, −]w

(w, ΞB, ξ|=m , ai . . . an )

∗

` (m0 , ΞB→C, ξ|=m , aj . . . an ) 0 0 ` (w, ΞB→C|=m F, ξ|=m |=m , aj . . . an )

0 0 [−, − | B, i, |=m , →C, j, |=m | −, −, −, −, −]m0 (m0 , C, ) 7−→ (w, C|=m F, |=m ) [−, − | C, j, |=m , |=m0 F, j, |=m0 | −, −, −, −, −]w Derivaciones que son el resultado de aplicar una transici´on (w, C, ) 7−→ (w, C→F, ) • a una derivaci´on de llamada, con las tres posibilidades siguientes:

(w, ΞA, ξ, ah . . . an )

∗

` (w, ΞA Ξ1 B, ξγγ 0 , ai . . . an ) ∗

` (w, ΞA Ξ1 B&C, ξγ, aj . . . an ) ` (w, ΞA Ξ1 B&C→F, ξγ, aj . . . an ) [A, h | B, i, γ 0 , &C, j, γ | −, −, −, −, −]w (w, C, ) 7−→ (w, C→F, ) [A, h | C, j, γ, →F, j, γ | −, −, −, −, −]w (w, ΞA, ξ, ah . . . an )

∗

` (w, ΞA Ξ1 B, ξγ, ai . . . an ) ∗

` (w, ΞA Ξ1 B→C, ξγ, aj . . . an ) ` (w, ΞA Ξ1 B→C→F, ξγ, aj . . . an ) [A, h | B, i, γ, →C, j, γ | −, −, −, −, −]w (w, C, ) 7−→ (w, C→F, ) [A, h | C, j, γ, →F, j, γ | −, −, −, −, −]w (w, ΞB, ξγ 0 , ai . . . an )

0

` (w, ΞB, ξγ 0 , ai . . . an ) ∗

` (w, ΞB%C, ξγ 0 γ, aj . . . an ) ` (w, ΞB%C→F, ξγ 0 γ, aj . . . an ) [B, i | B, i, γ 0 , %C, j, γ | −, −, −, −, −]w (w, C, ) 7−→ (w, C→F, ) [B, i | C, j, γ, →F, j, γ | −, −, −, −, −]w

10.3 Aut´ omatas con dos pilas fuertemente dirigidos • a una derivaci´on de puntos especiales, con las tres posibilidades siguientes: ∗

(m, ΞB, ξγ 0 , ai . . . an )

` (w, ΞB|=m C, ξγ 0 |=m , aj . . . an ) ` (w, ΞB|=m C→F, ξγ 0 |=m , aj . . . an )

[−, − | B, i, γ 0 , |=m C, j, |=m | −, −, −, −, −]w (w, C, ) 7−→ (w, C→F, ) [−, − | C, j, |=m , →F, j, |=m | −, −, −, −, −]w ∗

(w, ΞB, ξ|=m γ, ai . . . an )

` (w, ΞB&C, ξ|=m , aj . . . an ) ` (w, ΞB&C→F, ξ|=m , aj . . . an )

[−, − | B, i, γ, &C, j, |=m | −, −, −, −, −]w (w, C, ) 7−→ (w, C→F, ) [−, − | C, j, |=m , →F, j, |=m | −, −, −, −, −]w ∗

(w, ΞB, ξ|=m , ai . . . an )

` (w, ΞB→C, ξ|=m , aj . . . an ) ` (w, ΞB→C→F, ξ|=m , aj . . . an )

[−, − | B, i, |=m , →C, j, |=m | −, −, −, −, −]w (w, C, ) 7−→ (w, C→F, ) [−, − | C, j, |=m , →F, j, |=m | −, −, −, −, −]w Derivaciones que son el resultado de aplicar una transici´on (w, C, ) 7−→ (w, C%F, γ 0 ) • a una derivaci´on de llamada, con las tres posibilidades siguientes: (w, ΞA, ξ, ah . . . an )

∗

` (w, ΞA Ξ1 B, ξγγ 00 , ai . . . an ) ∗

` (w, ΞA Ξ1 B&C, ξγ, aj . . . an ) ` (w, ΞA Ξ1 B&C%F, ξγγ 0 , aj . . . an ) [A, h | B, i, γ 00 , &C, j, γ | −, −, −, −, −]w (w, C, ) 7−→ (w, C%F, γ 0 ) [C, j | C, j, γ, %F, j, γ 0 | −, −, −, −, −]w (w, ΞA, ξ, ah . . . an )

∗

` (w, ΞA Ξ1 B, ξγ, ai . . . an ) ∗

` (w, ΞA Ξ1 B→C, ξγ, aj . . . an ) ` (w, ΞA Ξ1 B→C%F, ξγγ 0 , aj . . . an ) [A, h | B, i, γ, →C, j, γ | −, −, −, −, −]w (w, C, ) 7−→ (w, C%F, γ 0 ) [C, j | C, j, γ, %F, j, γ 0 | −, −, −, −, −]w 0

(w, ΞB, ξγ 00 , ai . . . an )

` (w, ΞB, ξγ 00 , ai . . . an ) ∗

` (w, ΞB%C, ξγ 00 γ, aj . . . an ) ` (w, ΞB%C%F, ξγ 00 γγ 0 , aj . . . an ) [B, i | B, i, γ 00 , %C, j, γ | −, −, −, −, −]w (w, C, ) 7−→ (w, C%F, γ 0 ) [C, j | C, j, γ, %F, j, γ 0 | −, −, −, −, −]w • a una derivaci´on de puntos especiales, con las tres posibilidades siguientes: (m, ΞB, ξγ 00 , ai . . . an )

∗

` (w, ΞB|=m C, ξγ 00 |=m , aj . . . an ) ` (w, ΞB|=m C%F, ξγ 00 |=m γ 0 , aj . . . an )

[−, − | B, i, γ 00 , |=m C, j, |=m | −, −, −, −, −]w (w, C, ) 7−→ (w, C%F, γ 0 ) [C, j | C, j, |=m , %F, j, γ 0 | −, −, −, −, −]w

357

358

Aut´ omatas con dos pilas

(w, ΞB, ξ|=m γ, ai . . . an )

∗

` (w, ΞB&C, ξ|=m , aj . . . an ) ` (w, ΞB&C%F, ξ|=m γ 0 , aj . . . an )

[−, − | B, i, γ, &C, j, |=m | −, −, −, −, −]w (w, C, ) 7−→ (w, C%F, γ 0 ) [C, j | C, j, |=m , %F, j, γ 0 | −, −, −, −, −]w

(w, ΞB, ξ|=m , ai . . . an )

∗

` (w, ΞB→C, ξ|=m , aj . . . an ) ` (w, ΞB→C%F, ξ|=m γ 0 , aj . . . an )

[−, − | B, i, |=m , →C, j, |=m | −, −, −, −, −]w (w, C, ) 7−→ (w, C%F, γ 0 ) [C, j | C, j, |=m , %F, j, γ 0 | −, −, −, −, −]w Derivaciones que son el resultado de aplicar una transici´on (w, C, γ) 7−→ (w, C&F, ) a una derivaci´on de llamada, con las tres posibilidades siguientes: (w, ΞM, ξ, am . . . an )

∗

` (w, ΞM Ξ1 N, ξ 0 γ 000 , at . . . an ) ∗

` (w, ΞM Ξ1 N ⊗ A, ξγ 0 , ah . . . an ) ∗

` (w, ΞM Ξ1 N ⊗ A Ξ2 B, ξγ 0 γγ 00 , ai . . . an ) ∗

` (w, ΞM Ξ1 N ⊗ A Ξ2 B&C, ξγ 0 γ, aj . . . an ) ` (w, ΞM Ξ1 N ⊗ A Ξ2 B&C&F, ξγ 0 , aj . . . an ) [A, h | B, i, γ 00 , &C, j, γ | −, −, −, −, −]w [M, m | N, t, γ 000 , ⊗A, h, γ 0 | −, −, −, −, −]w [M, m | C, j, γ, &F, j, γ 0 | −, −, −, −, −]w

(w, ΞM, ξ, am . . . an )

(w, C, γ) 7−→ (w, C&F, )

∗

` (w, ΞM Ξ1 N, ξ 0 γ 000 , at . . . an ) ∗

` (w, ΞM Ξ1 N ⊗ A, ξγ 0 , ah . . . an ) ∗

` (w, ΞM Ξ1 N ⊗ A Ξ2 B, ξγ 0 γ, ai . . . an ) ∗

` (w, ΞM Ξ1 N ⊗ A Ξ2 B→C, ξγ 0 γ, aj . . . an ) ` (w, ΞM Ξ1 N ⊗ A Ξ2 B→C&F, ξγ 0 , aj . . . an ) [A, h | B, i, γ 00 , →C, j, γ | −, −, −, −, −]w [M, m | N, t, γ 000 , ⊗A, h, γ 0 | −, −, −, −, −]w [M, m | C, j, γ, &F, j, γ 0 | −, −, −, −, −]w

(w, ΞM, ξ, am . . . an )

(w, C, γ) 7−→ (w, C&F, )

∗

` (w, ΞM Ξ1 N, ξ 0 γ 000 , at . . . an ) ∗

` (w, ΞM Ξ1 N ⊗ B, ξγ 0 , ah . . . an ) 0

` (w, ΞM Ξ1 N ⊗ B, ξγ 0 , ai . . . an ) ∗

` (w, ΞM Ξ1 N ⊗ B%C, ξγ 0 γ, aj . . . an ) ` (w, ΞM Ξ1 N ⊗ B%C&F, ξγ 0 , aj . . . an ) [B, i | B, i, γ 0 , %C, j, γ | −, −, −, −, −]w [M, m | N, t, γ 000 , ⊗B, i, γ 0 | −, −, −, −, −]w [M, m | C, j, γ, &F, j, γ 0 | −, −, −, −, −]w

(w, C, γ) 7−→ (w, C&F, )

10.3 Aut´ omatas con dos pilas fuertemente dirigidos

359 a

Derivaciones que son el resultado de aplicar una transici´on (w, C, |=m ) 7−→ (e, F, |=m ) a una derivaci´on de puntos especiales, con los tres casos siguientes, en los cuales k = j si a =  y k = j + 1 si a ∈ VT : (m, ΞB, ξγ 0 , ai . . . an )

∗

` (w, ΞB|=m C, ξγ 0 |=m , aj . . . an ) ` (e, ΞB|=m F, ξγ 0 |=m , aj . . . an )

[−, − | B, i, γ 0 , |=m C, j, |=m | −, −, −, −, −]w a (w, C, |=m ) 7−→ (e, F, |=m ) [−, − | B, i, γ 0 , |=m F, k, |=m | −, −, −, −, −]e (w, ΞB, ξ|=m γ, ai . . . an )

∗

` (w, ΞB&C, ξ|=m , aj . . . an ) ` (e, ΞB&F, ξ|=m , aj . . . an )

[−, − | B, i, γ, &C, j, |=m | −, −, −, −, −]w a (w, C, |=m ) 7−→ (e, F, |=m ) [−, − | B, i, γ, &F, k, |=m | −, −, −, −, −]e (w, ΞB, ξ|=m , ai . . . an )

∗

` (w, ΞB→C, ξ|=m , aj . . . an ) ` (e, ΞB→F, ξ|=m , aj . . . an )

[−, − | B, i, |=m , →C, j, |=m | −, −, −, −, −]w a (w, C, |=m ) 7−→ (e, F, |=m ) [−, − | B, i, |=m , →F, k, |=m | −, −, −, −, −]e Derivaciones que son el resultado de aplicar una transici´on (e, C|=m F, |=m ) 7−→ (m, G, ) a una derivaci´on obtenida tras aplicar una transici´on (m, C, ) 7−→ (w, C|=m F 0 , |=m ) • a una derivaci´on de llamada, con los tres casos siguientes: (w, ΞA, ξ, ah . . . an )

∗

` (w, ΞA Ξ1 B, ξγγ 0 , ai . . . an ) ∗

` (w, ΞA Ξ1 B&C, ξγ, aj . . . an ) ` (w, ΞA Ξ1 B&C|=w F 0 , ξγ|=w , aj . . . an ) ∗ ` (e, ΞA Ξ B&C|=w F, ξγ|=w , a . . . a ) 1

k

n

` (w, ΞA Ξ1 B&G, ξγ, ak . . . an ) [−, − | C, j, γ, |=w F, k, |=w | −, −, −, −, −]e [A, h | B, i, γ 0 , &C, j, γ | −, −, −, −, −]w [A, h | B, i, γ 0 , &G, k, γ | −, −, −, −, −]w (w, ΞA, ξ, ah . . . an )

(e, C|=w F, |=w ) 7−→ (w, G, )

∗

` (w, ΞA Ξ1 B, ξγ, ai . . . an ) ∗

` (w, ΞA Ξ1 B→C, ξγ, aj . . . an ) ` (w, ΞA Ξ1 B→C|=w F 0 , ξγ|=w , aj . . . an ) ∗ ` (e, ΞA Ξ B→C|=w F, ξγ|=w , a . . . a ) 1

k

n

` (w, ΞA Ξ1 B→G, ξγ, ak . . . an ) [−, − | C, j, γ, |=w F, k, |=w | −, −, −, −, −]e [A, h | B, i, γ, →C, j, γ | −, −, −, −, −]w [A, h | B, i, γ, →G, k, γ | −, −, −, −, −]w (w, ΞB, ξγ 0 , ai . . . an )

(e, C|=w F, |=w ) 7−→ (w, G, )

0

` (w, ΞB, ξγ 0 , ai . . . an ) ∗

` (w, ΞB%C, ξγ 0 γ, aj . . . an ) ` (w, ΞB%C|=w F 0 , ξγ 0 γ|=w , aj . . . an ) ∗ ` (e, ΞB%C|=w F, ξγ 0 γ|=w , a . . . a ) k

` (w, ΞB%G, ξγ 0 γ, ak . . . an )

n

360

Aut´ omatas con dos pilas [−, − | C, j, γ, |=w F, k, |=w | −, −, −, −, −]e [B, i | B, i, γ 0 , %C, j, γ | −, −, −, −, −]w [B, i | B, i, γ 0 , %G, k, γ | −, −, −, −, −]w

(e, C|=w F, |=w ) 7−→ (w, G, )

• a una derivaci´on de retorno, con las tres posibilidades siguientes: ∗

` (w, ΞA Ξ1 B, ξγγ 0 , ai . . . an )

(w, ΞA, ξ, ah . . . an )

∗

` (w, ΞA Ξ1 B Ξ2 D, ξγ, ap . . . an ) ∗

` (e, ΞA Ξ1 B Ξ2 D&E, φ, aq . . . an ) ∗

` (e, ΞA Ξ1 B&C, φη, aj . . . an ) ` (w, ΞA Ξ1 B&C|=e F 0 , φη|=e , aj . . . an ) ∗ ` (e, ΞA Ξ B&C|=e F, φη|=e , a . . . a ) 1

k

n

` (e, ΞA Ξ1 B&G, φη, ak . . . an ) [−, − | C, j, η, |=e F, k, |=e | −, −, −, −, −]e [A, h | B, i, γ 0 , &C, j, η | D, p, γ, E, q]e [A, h | B, i, γ 0 , &G, k, η | D, p, γ, E, q]e

(e, C|=e F, |=e ) 7−→ (e, G, )

∗

` (w, ΞA Ξ1 B, ξγ, ai . . . an )

(w, ΞA, ξ, ah . . . an )

∗

` (w, ΞA Ξ1 B Ξ2 D, ξγ, ap . . . an ) ∗

` (e, ΞA Ξ1 B Ξ2 D&E, φ, aq . . . an ) ∗

` (e, ΞA Ξ1 B→C, φη, aj . . . an ) ` (w, ΞA Ξ1 B→C|=e F 0 , φη|=e , aj . . . an ) ∗ ` (e, ΞA Ξ B→C|=e F, φη|=e , a . . . a ) 1

k

n

` (e, ΞA Ξ1 B→G, φη, ak . . . an ) [−, − | C, j, η, |=e F, k, |=e | −, −, −, −, −]e [A, h | B, i, γ, →C, j, η | D, p, γ, E, q]e [A, h | B, i, γ, →G, k, η | D, p, γ, E, q]e (w, ΞB, ξγ 0 , ai . . . an )

(e, C|=e F, |=e ) 7−→ (e, G, )

0

` (w, ΞB, ξγ 0 , ai . . . an ) ∗

` (w, ΞB Ξ2 D, ξγ 0 γ, ap . . . an ) ∗

` (e, ΞB Ξ2 D&E, φη 0 , aq . . . an ) ∗

` (e, ΞB%C, φη 0 η, aj . . . an ) ` (w, ΞB%C|=e F 0 , φη 0 η|=e , aj . . . an ) ∗ ` (e, ΞB%C|=e F, φη 0 η|=e , a . . . a ) k

n

` (e, ΞB%G, φη 0 η, ak . . . an ) [−, − | C, j, η, |=e F, k, |=e | −, −, −, −, −]e [B, i | B, i, γ 0 , %C, j, η | D, p, γ, E, q]e [B, i | B, i, γ 0 , %G, k, η | D, p, γ, E, q]e

(e, C|=e F, |=e ) 7−→ (e, G, )

• a una derivaci´on de puntos especiales, con las tres posibilidades siguientes: (m, ΞB, ξγ 0 , ai . . . an )

∗

` (m0 , ΞB|=m C, ξγ 0 |=m , aj . . . an ) 0 0 ` (w, ΞB|=m C|=m F 0 , ξγ 0 |=m |=m , aj . . . an ) ∗

0

0

` (e, ΞB|=m C|=m F, ξγ 0 |=m |=m , ak . . . an ) ` (m0 , ΞB|=m G, ξγ 0 |=m , ak . . . an )

10.3 Aut´ omatas con dos pilas fuertemente dirigidos 0

361

0

[−, − | C, j, |=m , |=m F, k, |=m | −, −, −, −, −]e [A, h | B, i, γ 0 , |=m C, j, |=m | −, −, −, −, −]m0 [A, h | B, i, γ 0 , |=m G, k, |=m | −, −, −, −, −]m0 (w, ΞB, ξ|=m γ, ai . . . an )

0

0

(e, C|=m F, |=m ) 7−→ (m0 , G, )

∗

` (m0 , ΞB&C, ξ|=m , aj . . . an ) 0 0 ` (w, ΞB&C|=m F 0 , ξ|=m |=m , aj . . . an ) ∗

0

0

` (e, ΞB&C|=m F, ξ|=m |=m , ak . . . an ) ` (m0 , ΞB&C|=m F, ξ|=m |=m , ak . . . an ) 0

0

[−, − | C, j, |=m , |=m F, k, |=m | −, −, −, −, −]e [A, h | B, i, γ, &C, j, |=m | −, −, −, −, −]m0 [A, h | B, i, γ, &G, k, |=m | −, −, −, −, −]m0 (w, ΞB, ξ|=m , ai . . . an )

0

0

(e, C|=m F, |=m ) 7−→ (m0 , G, )

∗

` (m0 , ΞB→C, ξ|=m , aj . . . an ) 0 0 ` (w, ΞB→C|=m F 0 , ξ|=m |=m , aj . . . an ) ∗

0

0

` (e, ΞB→C|=m F, ξ|=m |=m , ak . . . an ) ` (m0 , ΞB→C|=m F, ξ|=m |=m , ak . . . an ) 0

0

[−, − | C, j, |=m , |=m F, k, |=m | −, −, −, −, −]e [A, h | B, i, |=m , →C, j, |=m | −, −, −, −, −]m0 [A, h | B, i, |=m , →G, k, |=m | −, −, −, −, −]m0

0

0

(e, C|=m F, |=m ) 7−→ (m0 , G, )

Derivaciones que son el resultado de aplicar una transici´on (e, C→F, ) 7−→ (e, G, ) a una derivaci´on obtenida tras aplicar una transici´on (w, C, ) 7−→ (w, C→F 0 , ) • a una derivaci´on de llamada, con las tres posibilidades siguientes: (w, ΞA, ξ, ah . . . an )

∗

` (w, ΞA Ξ1 B, ξγγ 0 , ai . . . an ) ∗

` (w, ΞA Ξ1 B&C, ξγ, aj . . . an ) ` (w, ΞA Ξ1 B&C→F 0 , ξγ, aj . . . an ) ∗

` (w, ΞA Ξ1 B&C→F 0 Ξ2 D, ξγ, ap . . . an ) ∗

` (e, ΞA Ξ1 B&C→F 0 Ξ2 D&E, φ, aq . . . an ) ∗

` (e, ΞA Ξ1 B&C→F, φη, ak . . . an ) ` (e, ΞA Ξ1 B&G, φη, ak . . . an ) [A, h | C, j, γ, →F, k, η | D, p, γ, E, q]e [A, h | B, i, γ 0 , &C, j, γ | −, −, −, −, −]w [A, h | B, i, γ 0 , &G, k, η | D, p, γ, E, q]e (w, ΞA, ξ, ah . . . an )

(e, C→F, ) 7−→ (e, G, )

∗

` (w, ΞA Ξ1 B, ξγ, ai . . . an ) ∗

` (w, ΞA Ξ1 B→C, ξγ, aj . . . an ) ` (w, ΞA Ξ1 B→C→F 0 , ξγ, aj . . . an ) ∗

` (w, ΞA Ξ1 B→C→F 0 Ξ2 D, ξγ, ap . . . an ) ∗

` (e, ΞA Ξ1 B→C→F 0 Ξ2 D&E, φ, aj . . . an ) ∗

` (e, ΞA Ξ1 B→C→F, φη, ak . . . an ) ` (e, ΞA Ξ1 B→G, φη, ak . . . an ) [A, h | C, j, γ, →F, k, η | D, p, γ, E, q]e [A, h | B, i, γ, →C, j, γ | −, −, −, −, −]w [A, h | B, i, γ, →G, k, η | D, p, γ, E, q]e

(e, C→F, ) 7−→ (e, G, )

362

Aut´ omatas con dos pilas

(w, ΞB, ξγ 0 , ai . . . an )

0

` (w, ΞB, ξγ 0 , ai . . . an ) ∗

` (w, ΞB%C, ξγ 0 γ, aj . . . an ) ` (w, ΞB%C→F 0 , ξγ 0 γ, aj . . . an ) ∗

` (w, ΞB%C→F 0 Ξ2 D, ξγ 0 γ, ap . . . an ) ∗

` (e, ΞB%C→F 0 Ξ2 D&E, φη 0 , aq . . . an ) ∗

` (e, ΞB%C→F, φη 0 η, ak . . . an ) ` (e, ΞB%G, φη 0 η, ak . . . an ) [B, i | C, j, γ, →F, k, η | D, p, γ, E, q]e [B, i | B, i, γ 0 , %C, j, γ | −, −, −, −, −]w [B, i | B, i, γ 0 , %G, k, η | D, p, γ, E, q]e

(e, C→F, ) 7−→ (e, G, )

• a una derivaci´on de puntos especiales, con las tres posibilidades siguientes: (m, ΞB, ξγ 0 , ai . . . an )

∗

` (w, ΞB|=m C, ξγ 0 |=m , aj . . . an ) ` (w, ΞB|=m C→F 0 , ξγ 0 |=m , aj . . . an ) ∗

` (e, ΞB|=m C→F, ξγ 0 |=m , ak . . . an ) ` (e, ΞB|=m G, ξγ 0 |=m , ak . . . an ) [−, − | C, j, |=m , →F, k, |=m | −, −, −, −, −]e [−, − | B, i, γ 0 , |=m C, j, |=m | −, −, −, −, −]w [−, − | B, i, γ 0 , |=m G, k, |=m | −, −, −, −, −]e

(w, ΞB, ξ|=m γ, ai . . . an )

(e, C→F, ) 7−→ (e, G, )

∗

` (w, ΞB&C, ξ|=m , aj . . . an ) ` (w, ΞB&C→F 0 , ξ|=m , aj . . . an ) ∗

` (e, ΞB&C→F, ξ|=m , ak . . . an ) ` (e, ΞB&G, ξ|=m , ak . . . an ) [−, − | C, j, |=m , →F, k, |=m | −, −, −, −, −]e [−, − | B, i, γ, &C, j, |=m | −, −, −, −, −]w [−, − | B, i, γ, &G, k, |=m | −, −, −, −, −]e

(w, ΞB, ξ|=m , ai . . . an )

(e, C→F, ) 7−→ (e, G, )

∗

` (w, ΞB→C, ξ|=m , aj . . . an ) ` (w, ΞB→C→F 0 , ξ|=m , aj . . . an ) ∗

` (e, ΞB→C→F, ξ|=m , ak . . . an ) ` (e, ΞB→G, ξ|=m , ak . . . an ) [−, − | C, j, |=m , →F, k, |=m | −, −, −, −, −]e [−, − | B, i, |=m , →C, j, |=m | −, −, −, −, −]w [−, − | B, i, |=m , →G, k, |=m | −, −, −, −, −]e

(e, C→F, ) 7−→ (e, G, )

Derivaciones que son el resultado de aplicar una transici´on (e, C%F, η 0 ) 7−→ (e, G, ) a una derivaci´on obtenida tras aplicar una transici´on (w, C, ) 7−→ (w, C%F 0 , γ 0 )

10.3 Aut´ omatas con dos pilas fuertemente dirigidos

363

• a una derivaci´on de llamada, con los tres casos siguientes: (w, ΞA, ξ, ah . . . an )

∗

` (w, ΞA Ξ1 B, ξγγ 00 , ai . . . an ) ∗

` (w, ΞA Ξ1 B&C, ξγ, aj . . . an ) ` (w, ΞA Ξ1 B&C%F 0 , ξγγ 0 , aj . . . an ) ∗

` (w, ΞA Ξ1 B&C%F 0 Ξ2 D, ξγγ 0 , ap . . . an ) ∗

` (w, ΞA Ξ1 B&C%F 0 Ξ2 D Ξ3 O, ξγ, u . . . an ) ∗

` (e, ΞA Ξ1 B&C%F 0 Ξ2 D Ξ3 O&P, φ, v . . . an ) ∗

` (e, ΞA Ξ1 B&C%F 0 Ξ2 D&E, φη, aq . . . an ) ∗

` (e, ΞA Ξ1 B&C%F, φηη 0 , ak . . . an ) ` (e, ΞA Ξ1 B&G, φη, ak . . . an ) [C, j | C, j, γ, %F, k, η 0 | D, p, γ 0 , E, q]e [A, h | B, i, γ 00 , &C, j, γ | −, −, −, −, −]w [A, h | D, p, γ 0 , &E, q, η | O, u, γ, P, v]e [A, h | B, i, γ 00 , &G, k, η | O, u, γ, P, v]e (w, ΞA, ξ, ah . . . an )

(e, C%F, η 0 ) 7−→ (e, G, )

∗

` (w, ΞA Ξ1 B, ξγ, ai . . . an ) ∗

` (w, ΞA Ξ1 B→C, ξγ, aj . . . an ) ` (w, ΞA Ξ1 B→C%F 0 , ξγγ 0 , aj . . . an ) ∗

` (w, ΞA Ξ1 B→C%F 0 Ξ2 D, ξγγ 0 , aj . . . an ) ∗

` (w, ΞA Ξ1 B→C%F 0 Ξ2 D Ξ2 O, ξγ, au . . . an ) ∗

` (e, ΞA Ξ1 B→C%F 0 Ξ2 D Ξ2 O&P, φ, av . . . an ) ∗

` (e, ΞA Ξ1 B→C%F 0 Ξ2 D&E, φη, aj . . . an ) ∗

` (e, ΞA Ξ1 B→C%F, φηη 0 , ak . . . an ) ` (e, ΞA Ξ1 B→G, φη, ak . . . an ) [C, j | C, j, γ, %F, k, η 0 | D, p, γ 0 , E, q]e [A, h | B, i, γ, →C, j, γ | −, −, −, −, −]w [A, h | D, p, γ 0 , &E, q, η | O, u, γ, P, v]e [A, h | B, i, γ, →G, k, η | O, u, γ, P, v]e (w, ΞB, ξγ 00 , ai . . . an )

(e, C%F, η 0 ) 7−→ (e, G, )

0

` (w, ΞB, ξγ 00 , ai . . . an ) ∗

` (w, ΞB%C, ξγ 00 γ, aj . . . an ) ` (w, ΞB%C%F 0 , ξγ 00 γγ 0 , aj . . . an ) ∗

` (w, ΞB%C%F 0 Ξ1 D, ξγ 00 γγ 0 , ap . . . an ) ∗

` (w, ΞB%C%F 0 Ξ1 D Ξ2 O, ξγ 00 γ, au . . . an ) ∗

` (e, ΞB%C%F 0 Ξ1 D Ξ2 O&P, φη 00 , av . . . an ) ∗

` (e, ΞB%C%F 0 Ξ1 D&E, φη 00 η, aq . . . an ) ∗

` (e, ΞB%C%F, φη 00 ηη 0 , ak . . . an ) ` (e, ΞB%G, φη 00 η, ak . . . an ) [C, j | C, j, γ, %F, k, η 0 | D, p, γ 0 , E, q]e [B, i | B, i, γ 00 , %C, j, γ | −, −, −, −, −]w [B, i | D, p, γ 0 , &E, q, η | O, u, γ, P, v]e [B, i | B, i, γ 00 , %G, k, η | O, u, γ, P, v]e

(e, C%F, η 0 ) 7−→ (e, G, )

364

Aut´ omatas con dos pilas • a una derivaci´on de puntos especiales, con los dos casos siguientes: (m, ΞB, ξγ 00 , ai . . . an )

∗

` (w, ΞB|=m C, ξγ 00 |=m , aj . . . an ) ` (w, ΞB|=m C%F 0 , ξγ 00 |=m γ 0 , aj . . . an ) ∗

` (w, ΞB|=m C%F 0 Ξ1 D, ξγ 00 |=m γ 0 , ap . . . an ) ∗

` (e, ΞB|=m C%F 0 Ξ1 D&E, ξγ 00 |=m , aq . . . an ) ∗

` (e, ΞB|=m C%F, ξγ 00 |=m η 0 , ak . . . an ) ` (e, ΞB|=m G, ξγ 00 |=m , ak . . . an ) [C, j | C, j, |=m , %F, k, η 0 | D, p, γ 0 , E, q]e [−, − | B, i, γ 00 , |=m C, j, |=m | −, −, −, −, −]w [−, − | D, p, γ 0 , &E, q, |=m | −, −, −, −, −]e [−, − | B, i, γ 00 , |=m G, k, |=m | −, −, −, −, −]e (w, ΞB, ξ|=m γ, ai . . . an )

(e, C%F, η 0 ) 7−→ (e, G, )

∗

` (w, ΞB&C, ξ|=m , aj . . . an ) ` (w, ΞB&C%F 0 , ξ|=m γ 0 , aj . . . an ) ∗

` (w, ΞB&C%F 0 Ξ1 D, ξ|=m γ 0 , ap . . . an ) ∗

` (e, ΞB&C%F 0 Ξ1 D&E, ξ|=m , aq . . . an ) ∗

` (e, ΞB&C%F, ξ|=m η 0 , ak . . . an ) ` (e, ΞB&G, ξ|=m , ak . . . an ) [C, j | C, j, |=m , %F, k, η 0 | D, p, γ 0 , E, q]e [−, − | B, i, γ, &C, j, |=m | −, −, −, −, −]w [−, − | D, p, γ 0 , &E, q, |=m | −, −, −, −, −]e [−, − | B, i, γ, &G, k, |=m | −, −, −, −, −]e (w, ΞB, ξ|=m , ai . . . an )

(e, C%F, η 0 ) 7−→ (e, G, )

∗

` (w, ΞB→C, ξ|=m , aj . . . an ) ` (w, ΞB→C%F 0 , ξ|=m γ 0 , aj . . . an ) ∗

` (w, ΞB→C%F 0 Ξ1 D, ξ|=m γ 0 , ap . . . an ) ∗

` (e, ΞB→C%F 0 Ξ1 D&E, ξ|=m , aq . . . an ) ∗

` (e, ΞB→C%F, ξ|=m η 0 , ak . . . an ) ` (e, ΞB→G, ξ|=m , ak . . . an ) [C, j | C, j, |=m , %F, k, η 0 | D, p, γ 0 , E, q]e [−, − | B, i, |=m , →C, j, |=m | −, −, −, −, −]w [−, − | D, p, γ 0 , &E, q, |=m | −, −, −, −, −]e (e, C%F, η 0 ) 7−→ (e, G, ) [−, − | B, i, |=m , →G, k, |=m | −, −, −, −, −]e Derivaciones que son el resultado de aplicar una transici´on (e, C&F, ) 7−→ (e, G, η) a una derivaci´on obtenida tras aplicar una transici´on (w, C, γ) 7−→ (w, C&F, ) a una derivaci´on de llamada, con los tres casos siguientes: (w, ΞM, ξ, am . . . an )

∗

` (w, ΞM Ξ1 N, ξ 0 γ 000 , at . . . an ) ∗

` (w, ΞM Ξ1 N ⊗ A, ξγ 0 , ah . . . an ) ∗

` (w, ΞM Ξ1 N ⊗ A Ξ2 B, ξγ 0 γγ 00 , ai . . . an ) ∗

` (w, ΞM Ξ1 N ⊗ A Ξ2 B&C, ξγ 0 γ, aj . . . an ) ` (w, ΞM Ξ1 N ⊗ A Ξ2 B&C&F 0 , ξγ 0 , aj . . . an ) ∗

` (w, ΞM Ξ1 N ⊗ A Ξ2 B&C&F 0 Ξ4 D, ξγ 0 , ap . . . an ) ∗

` (e, ΞM Ξ1 N ⊗ A Ξ2 B&C&F 0 Ξ4 D&E, φ, aq . . . an ) ∗

` (e, ΞM Ξ1 N ⊗ A Ξ2 B&C&F, φη 0 , ak . . . an ) ` (e, ΞM Ξ1 N ⊗ A Ξ2 B&G, φη 0 η, ak . . . an )

10.3 Aut´ omatas con dos pilas fuertemente dirigidos [M, m | C, j, γ, &F, k, η 0 | D, p, γ 0 , E, q]e [A, h | B, i, γ 00 , &C, j, γ | −, −, −, −, −]w [M, m | N, t, γ 000 , ⊗A, h, γ 0 | −, −, −, −, −]w [A, h | B, i, γ 00 , &G, k, η | C, j, γ, &F, k]e

(w, ΞM, ξ, am . . . an )

365

(e, C&F, ) 7−→ (e, G, η)

∗

` (w, ΞM Ξ1 N, ξ 0 γ 000 , at . . . an ) ∗

` (w, ΞM Ξ1 N ⊗ A, ξγ 0 , ah . . . an ) ∗

` (w, ΞM Ξ1 N ⊗ A Ξ2 B, ξγ 0 γ, ai . . . an ) ∗

` (w, ΞM Ξ1 N ⊗ A Ξ2 B→C, ξγ 0 γ, aj . . . an ) ` (w, ΞM Ξ1 N ⊗ A Ξ2 B→C&F 0 , ξγ 0 , aj . . . an ) ∗

` (w, ΞM Ξ1 N ⊗ A Ξ2 B→C&F 0 Ξ3 D, ξγ 0 , ap . . . an ) ∗

` (e, ΞM Ξ1 N ⊗ A Ξ2 B→C&F 0 Ξ3 D&E, φ, aq . . . an ) ∗

` (e, ΞM Ξ1 N ⊗ A Ξ2 B→C&F, φη 0 , ak . . . an ) ` (e, ΞM Ξ1 N ⊗ A Ξ2 B→G, φη 0 η, ak . . . an ) [M, m | C, j, γ, &F, k, η 0 | D, p, γ 0 , E, q]e [A, h | B, i, γ, →C, j, γ | −, −, −, −, −]w [M, m | N, t, γ 000 , ⊗A, h, γ 0 | −, −, −, −, −]w [A, h | B, i, γ, →G, k, η | C, j, γ, &F, k]e

(w, ΞM, ξ, am . . . an )

(e, C&F, ) 7−→ (e, G, η)

∗

` (w, ΞM Ξ1 N, ξ 0 γ 000 , at . . . an ) ∗

` (w, ΞM Ξ1 N ⊗ B, ξγ 0 , ah . . . an ) 0

` (w, ΞM Ξ1 N ⊗ B, ξγ 0 , ai . . . an ) ∗

` (w, ΞM Ξ1 N ⊗ B%C, ξγ 0 γ, aj . . . an ) ` (w, ΞM Ξ1 N ⊗ B%C&F 0 , ξγ 0 , aj . . . an ) ∗

` (w, ΞM Ξ1 N ⊗ B%C&F 0 Ξ2 D, ξγ 0 , ap . . . an ) ∗

` (e, ΞM Ξ1 N ⊗ B%C&F 0 Ξ2 D&E, φ, aq . . . an ) ∗

` (e, ΞM Ξ1 N ⊗ B%C&F, φη 0 , ak . . . an ) ` (e, ΞM Ξ1 N ⊗ B%G, φη 0 η, ak . . . an ) [M, m | C, j, γ, &F, k, η 0 | D, p, γ 0 , E, q]e [B, i | B, i, γ 0 , %C, j, γ | −, −, −, −, −]w [M, m | N, t, γ 000 , ⊗A, h, γ 0 | −, −, −, −, −]w [B, i | B, i, γ 0 , %G, k, η | C, j, γ, &F, k]e

(e, C&F, ) 7−→ (e, G, η)

A partir de esta lista se puede mostrar por inducci´on en la longitud de las derivaciones que tanto mediante la manipulaci´on de configuraciones como mediante la manipulaci´on de ´ıtems se obtienen los mismos resultados. 2

La complejidad espacial de la t´ecnica de tabulaci´on propuesta con respecto a la longitud n de la cadena de entrada es O(n5 ) puesto que en cada ´ıtem se almacenan 5 posiciones de la cadena de entrada. La complejidad temporal en el peor caso es O(n7 ) y viene dada por la regla [C, j | C, j, γ, %F, k, η 0 | D, p, γ 0 , E, q]e [A, h | B, i, γ 00 , ⊗C, j, γ | −, −, −, −, −]w [A, h | D, p, γ 0 , &E, q, η | O, u, γ, P, v]e [A, h | B, i, γ 00 , ⊗G, k, η | O, u, γ, P, v]e

(e, C%F, η 0 ) 7−→ (e, G, )

366

Aut´ omatas con dos pilas

Esta regla involucra la combinaci´on de 8 posiciones de la cadena de entrada, aunque mediante aplicaci´on parcial s´olo es preciso utilizar 7 de dichas posiciones simult´aneamente, combinando el primer y tercer ´ıtem antecedente y despu´es combinando el resultado obtenido con el segundo ´ıtem antecedente para obtener finalmente el ´ıtem consecuente. Tal y como muestran De la Clergerie y Alonso Pardo en [53], esta complejidad puede reducirse a O(n6 ) mediante el particionamiento de la regla anterior en las dos reglas siguientes: [C, j | C, j, γ, %F, k, η 0 | D, p, γ 0 , E, q]e [A, h | D, p, γ 0 , &E, q, η | O, u, γ, P, v]e [[C, j, γ, %F, k, η 0 | O, u, γ, P, v]]e [[C, j, γ, %F, k, η 0 | O, u, γ, P, v]]e [A, h | B, i, γ 00 , ⊗C, j, γ | −, −, −, −, −]w [A, h | D, p, γ 0 , &E, q, η | O, u, γ, P, v]e [A, h | B, i, γ 00 , ⊗G, k, η | O, u, γ, P, v]e

(e, C%F, η 0 ) 7−→ (e, G, )

(e, C%F, η 0 ) 7−→ (e, G, )

La primera regla combina el primer y tercer ´ıtem antecedente de la regla original, teniendo como consecuente un pseudo-´ıtem que permitir´a transmitir parte de la informaci´on presente en los antecedentes a la segunda regla. En particular, es de destacar que la primera regla obvia los campos (A, h). Esta informaci´on es recuperada por la segunda regla mediante la combinaci´on del pseudo-´ıtem con el segundo y tercer ´ıtem antecedente de la regla original. El ´ıtem consecuente de la segunda regla coincide con el ´ıtem consecuente de la regla original, por lo que la aplicaci´on combinada de las dos reglas propuestas es equivalente a la aplicaci´on de la regla original. Sin embargo, hemos logrado reducir la complejidad temporal de O(n7 ) a O(n6 ), ya que que la primera regla tiene una complejidad O(n6 ) (la posici´on h no interviene), la misma complejidad que presenta la segunda regla, en cuya aplicaci´on las posiciones p y q no intervienen.

10.4.

Aut´ omatas con dos pilas ascendentes

Los aut´omatas con dos pilas fuertemente dirigidos pueden ser utilizados para implementar estrategias de an´alisis sint´actico para gram´aticas de adjunci´on de a´rboles independientemente de que las adjunciones se traten de manera descendente o ascendente. Esta potencia expresiva tiene como contrapunto la complejidad espacial O(n5 ) de la interpretaci´on tabular para esta clase de aut´omatas, cuando los algoritmos tabulares de an´alisis sint´actico que u ´nicamente consideran el tratamiento ascendente de la adjunci´on presentan una complejidad O(n 4 ) (v´ease el cap´ıtulo 3). Con respecto a la complejidad temporal, en los algoritmos ascendentes se obtiene O(n 6 ) de forma directa, mientras que en los aut´omatas con dos pilas fuertemente dirigidos se obtiene el mismo resultado tras aplicar una sofisticada optimizaci´on. Las mismas consideraciones son aplicables a las gram´aticas lineales de ´ındices con respecto al tratamiento de las pilas de ´ındices: aquellos algoritmos que eval´ uan las pilas de ´ındices de forma ascendente presentan menos complejidad espacial y temporal (v´ease el cap´ıtulo 4). En este contexto, surge la cuesti´on de si es posible dise˜ nar una versi´on de los SD–2SA especializada en el tratamiento ascendente de la pila auxiliar que rivalice en cuanto a complejidad especial y temporal con los algoritmos tabulares para el an´alisis sint´actico de LIG y TAG. Definimos un aut´ omata con dos pilas ascendente (Bottom-up 2–Stack Automata, BU–2SA) como un aut´omata con dos pilas fuertemente dirigido sobre el cual se establece la restricci´on adicional de que las sesiones de la pila auxiliar deben permanecer vac´ıas durante el modo de escritura. M´as formalmente, un aut´omata con dos pilas ascendente se define mediante una tupla (VT , VS , $0 , $f , VI , D0 , Θ) donde VT es un conjunto finito de s´ımbolos terminales.

10.4 Aut´ omatas con dos pilas ascendentes

367

VS es un conjunto finito de s´ımbolos de la pila maestra. $0 ∈ VS es el s´ımbolo inicial de la pila maestra. $f ∈ VS es el s´ımbolo final de la pila maestra. VI es un conjunto finito de s´ımbolos de la pila auxiliar. D0 = {|=w , |=e , } es el conjunto de marcas de adjunci´on, resultado de proyectar el conjunto D = {|=w , |=e , %, →, &} utilizado por los aut´omatas con dos pilas fuertemente dirigidos. Θ es un conjunto finito de transiciones. Una configuraci´ on de un aut´omata con dos pilas ascendente es una tupla (m, Ξ, ξ, w), donde m ∈ {w, e}, Ξ ∈ (D 0 VS )∗ , ξ ∈ (D0 VI∗ )∗ y w ∈ VT∗ . Los conceptos de derivaci´ on y lenguaje aceptado se definen de modo id´entico a como se hace para los aut´omatas con dos pilas fuertemente dirigidos. El conjunto de transiciones de los aut´omatas con dos pilas ascendentes debe garantizar que las sesiones de la pila auxiliar permanecen vac´ıas durante el modo de escritura, obteni´endose como resultado el siguiente juego de transiciones: a

SWAP1 : Transiciones de la forma (m, C, ) 7−→ (m, F, ), donde m ∈ {w, e}, C, F ∈ VS y a ∈ VT ∪ . El resultado de aplicar una transici´on de este tipo a una configuraci´on (m, ΞC, ξ, aw) es una configuraci´on (m, ΞF, ξ, w). a

SWAP2 : Transiciones de la forma (w, C, |=m ) 7−→ (e, F, |=m ). El resultado de aplicar una transici´on este tipo a una configuraci´on (m, ΞC, ξ|=m , aw) es una configuraci´on (m, ΞF, ξ|=m , w). Estas transiciones son las u ´nicas que permiten pasar del modo de escritura al modo de borrado. |=WRITE : Transiciones de la forma (m, C, ) 7−→ (w, C|=m F, |=m ) que al ser aplicadas a una configuraci´on (m, ΞC, ξ, w) producen una configuraci´on (w, ΞC|=m F, ξ|=m ). WRITE : Transiciones de la forma (w, C, ) 7−→ (w, C  F, ) que al ser aplicadas a una transici´on (w, ΞC, ξ|=m , w) producen una configuraci´on (w, ΞC  F, ξ|=m , w). |=ERASE : Transiciones de la forma (e, C|=m F, |=m ) 7−→ (m, G, ) que al ser aplicadas a una configuraci´on (m, ΞC|=m F, ξ|=m , w) producen una configuraci´on (m, ΞG, ξ, w). →ERASE : Transiciones de la forma (e, C  F, ) 7−→ (e, G, ) que al ser aplicadas a una configuraci´on (e, ΞC  F, ξ, w) producen una configuraci´on (e, ΞG, ξ, w). %ERASE : Transiciones de la forma (e, C  F, η 0 ) 7−→ (e, G, ) que al ser aplicadas a una configuraci´on (e, ΞC  F, ξη 0 , w) producen una configuraci´on (e, ΞG, ξ, w). &ERASE : Transiciones de la forma (e, C  F, ) 7−→ (e, G, η) que al ser aplicadas a una configuraci´on (e, ΞC  F, ξ, w) producen una configuraci´on (e, ΞG, ξη, w). Como se puede observar, este juego de transiciones es el resultado de proyectar el conjunto D en el conjunto D 0 . Como resultado, las marcas %, → y & son sustituidas por una u ´nica marca , con lo cual no se predice ninguna informaci´on acerca de la formaci´on de la pila auxiliar durante el modo de escritura.

368

Aut´ omatas con dos pilas

10.4.1.

Esquemas de compilaci´ on de gram´ aticas lineales de ´ındices

Al igual que en el caso de los aut´omatas con dos pilas fuertemente dirigidos, utilizaremos la pila maestra para almacenar no-terminales de la gram´atica y la pila auxiliar para almacenar los ´ındices. El esquema de compilaci´on gen´erico se define en funci´on de los siguientes par´ametros: → − A , la predicci´on realizada sobre el no-terminal A durante la fase descendente de la estrategia de an´alisis. ← − A , la propagaci´on de informaci´on respecto al no-terminal A durante la fase ascendente de la estrategia de an´alisis.

Esquema de compilaci´ on 10.3 El esquema de compilaci´on gen´erico de una gram´atica lineal de ´ındices en un aut´omata con dos pilas ascendente queda definido por el conjunto de reglas ← − mostrado en la tabla 10.8 y por los elementos inicial $0 y final S . Este esquema se puede convertir en esquemas de compilaci´on que incorporan estrategias espec´ıficas. En la tabla 10.9 se muestran los valores que toman los diferentes par´ametros para las estrategias de an´alisis de LIG m´as comunes. En dicha tabla,  indica un s´ımbolo de pila especial que no aparece inicialmente en VS . §

[INIT]

(w, $0 , ) 7−→ (w, $0 |=w ∇0,0 , |=w )

[CALL]

−−−−→ (m, ∇r,s , ) 7−→ (w, ∇r,s |=m Ar,s+1 , |=m )

Ar,0 [◦◦γ] → Υ1 Ar,s+1 [ ]Υ2

[SCALL]

−−−−→ (w, ∇r,s , ) 7−→ (w, ∇r,s  Ar,s+1 , )

Ar,0 [◦◦γ] → Υ1 Ar,s+1 [◦◦γ 0 ]Υ2

[SEL]

−−→ (w, Ar,0 , ) 7−→ (w, ∇r,0 , )

r 6= 0

[PUB]

←−− (e, ∇r,nr , ) 7−→ (e, Ar,0 , )

[RET]

←−−−− (e, ∇r,s |=m Ar,s+1 , |=m ) 7−→ (m, ∇r,s+1 , )

Ar,0 [◦◦γ] → Υ1 Ar,s+1 [ ]Υ2

←−−−− [SRET-1] (e, ∇r,s  Ar,s+1 , ) 7−→ (e, ∇r,s+1 , )

Ar,0 [◦◦] → Υ1 Ar,s+1 [◦◦]Υ2

←−−−− [SRET-2] (e, ∇r,s  Ar,s+1 , γ 0 ) 7−→ (e, ∇r,s+1 , )

Ar,0 [◦◦] → Υ1 Ar,s+1 [◦◦γ 0 ]Υ2

←−−−− [SRET-3] (e, ∇r,s  Ar,s+1 , ) 7−→ (e, ∇r,s+1 , γ)

Ar,0 [◦◦γ] → Υ1 Ar,s+1 [◦◦]Υ2

[SCAN]

−−→ ←−− a (w, Ar,0 , |=m ) 7−→ (e, Ar,0 , |=m )

Ar,0 [ ] → a

Tabla 10.8: Reglas del esquema de compilaci´on gen´erico de LIG en BU–2SA

10.4.2.

Esquemas de compilaci´ on para gram´ aticas de adjunci´ on de ´ arboles

Al igual que en el caso de los aut´omatas con dos pilas fuertemente dirigidos, utilizaremos la pila maestra para almacenar los nodos de los a´rboles elementales y la pila auxiliar para almacenar

10.4 Aut´ omatas con dos pilas ascendentes

369

estrategia-CF

−−−−→ Ar,s+1

←−−−− Ar,s+1

Ascendente



Ar,s+1

Earley

Ar,s+1

Ar,s+1

Descendente

Ar,s+1



Tabla 10.9: Par´ametros del esquema de compilaci´on gen´erico de LIG en SD–2SA la pila de adjunciones pendiente en cada nodo. El esquema de compilaci´on gen´erico mediante la parametrizaci´on del flujo de informaci´on de las fases de llamada y retorno. Los par´ametros a considerar son: −−→ γ γ Nr,s , la informaci´on predicha acerca del nodo Nr,s . ←−γ− γ Nr,s , la informaci´on propagada acerca del nodo Nr,s .

Esquema de compilaci´ on 10.4 El esquema de compilaci´on gen´erico de una gram´atica de adjunci´on de a´rboles en un aut´omata con dos pilas ascendente queda definido por el conjunto de ←− reglas mostrado en la tabla 10.10 y los elementos inicial $0 y final >α , con α ∈ I. Este esquema se puede convertir en esquemas de compilaci´on para diferentes estrategias de an´alisis seg´ un los valores que tomen los par´ametros, tal y como se indica en la tabla 10.11. §

10.4.3.

BU–2SA y los lenguajes de adjunci´ on de ´ arboles

Los lenguajes aceptados por los aut´omatas con dos pilas ascendentes coinciden con los lenguajes de adjunci´on de a´rboles. Para demostrar esta aseveraci´on definiremos y demostraremos los dos teoremas siguientes. Teorema 10.6 Los lenguajes adjunci´ on de a ´rboles son un subconjunto de los lenguajes aceptados por la clase de los aut´ omatas con dos pilas ascendentes. Demostraci´on: Por el esquema de compilaci´on de TAG en BU–2SA presentado anteriormente, a partir de cualquier gram´atica de adjunci´on de a´rboles es posible construir un SD–2SA que acepta el lenguaje reconocido por dicha gram´atica. 2

Teorema 10.7 La clase de los lenguajes aceptados por los aut´ omatas con dos pilas ascendentes es un subconjunto de los lenguajes de adjunci´ on de a ´rboles. Demostraci´on: Mostraremos que para todo SD–2SA existe una gram´atica lineal de ´ındices tal que el lenguaje reconocido por la gram´atica coincide con el lenguaje aceptado por el aut´omata. Sea A = (VT , VS , $0 , $f , VI , D0 , Θ) un aut´omata lineal de ´ındices ascendente. Construiremos una gram´atica lineal de ´ındices L = (VT , VN , VI , S, P ). El conjunto VN de no-terminales estar´a formado por pares hE, Bi tal que A, B ∈ VS . Para que L reconozca el lenguaje aceptado por A el conjunto de producciones en P ha de construirse a partir de las transiciones en Θ de la siguiente manera:

370

Aut´ omatas con dos pilas

[INIT]

(w, $0 , ) 7−→ (w, $0 |=w ∇α0,0 , |=w )

α∈I

[CALL]

−−− → m γ− (m, ∇γr,s , ) 7−→ (w, ∇γr,s |=m Nr,s+1 , |= )

γ Nr,s+1 6∈ espina(γ), nil ∈ adj(Nr,s+1 )

[SCALL]

−−− → γ− (w, ∇γr,s , ) 7−→ (w, ∇γr,s  Nr,s+1 , )

γ Nr,s+1 ∈ espina(γ), nil ∈ adj(Nr,s+1 )

[SEL]

−−→ γ , ) 7−→ (w, ∇γr,0 , ) (w, Nr,0

r 6= 0

[PUB1]

←−γ− (e, ∇γr,nr , ) 7−→ (e, Nr,0 , )

[PUB2]

←−γ− m , |= ) (w, ∇γr,nr , |=m ) 7−→ (e, Nr,0

[RET]

←−γ−−− m γ 6∈ espina(γ), nil ∈ adj(Nr,s+1 ) , |= ) 7−→ (m, ∇γr,s+1 , ) Nr,s+1 (e, ∇γr,s |=m Nr,s+1

[SRET]

←−γ−−− (e, ∇γr,s  Nr,s+1 , ) 7−→ (e, ∇γr,s+1 , )

[SCAN]

−−→ ←−γ− m a γ (w, Nr,0 , |=m ) 7−→ (e, Nr,0 , |= )

−−→ [ACALL] (w, ∇γr,s , ) 7−→ (w, ∇γr,s  >β , )

γ Nr,s+1 ∈ espina(γ), nil ∈ adj(Nr,s+1 ) γ Nr,0 []→a γ β ∈ adj(Nr,s+1 )

[ARET]

←− γ (e, ∇γr,s  >β , Nr,s+1 ) 7−→ (e, ∇γr,s+1 , )

γ β ∈ adj(Nr,s+1 )

[FCALL]

−−− → γ− (w, ∇βf,0 , ) 7−→ (w, ∇βf,0  Nr,s+1 , )

β γ Nf,0 = Fβ , β ∈ adj(Nr,s+1 )

[FRET]

←−γ−−− γ β γ (w, ∇βf,0  Nr,s+1 , ) 7−→ (e, ∇βf,1 , Nr,s+1 ) Nf,0 = Fβ , β ∈ adj(Nt,s+1 )

Tabla 10.10: Reglas del esquema de compilaci´on gen´erico de TAG en BU–2SA a

Para toda transici´on (m, C, ) 7−→ (m, F, ) y para todo E ∈ P creamos una producci´on hE, F i[◦◦] → hE, Ci[◦◦] a a

Para toda transici´on (w, C, |=m ) 7−→ (e, F, |=m ) y para todo E ∈ P creamos una producci´on hE, F i[◦◦] → hE, Ci[◦◦] a a

Para toda transici´on (w, C, ) 7−→ (w, C  F, ) creamos una producci´on hC, F i[ ] →  Para toda transici´on (m, C, ) 7−→ (w, C|=m F, |=m ) creamos una producci´on hC, F i[ ] →  Para toda transici´on (e, C|=m F, |=m ) 7−→ (m, G, ) y para todo E ∈ P creamos una producci´on hE, Gi[◦◦] → hE, Ci[◦◦] hC, F i[ ] Para toda transici´on (e, C  F, ) 7−→ (e, G, ) y para todo E ∈ P creamos una producci´on hE, Gi[◦◦] → hE, Ci[ ] hC, F i[◦◦]

10.4 Aut´ omatas con dos pilas ascendentes

371

Estrategia-CF

−−− → γ− Nr,s+1

←−γ−−− Nr,s+1

Ascendente



γ Nr,s+1

Earley

γ Nr,s+1

γ Nr,s+1

Descendente

γ Nr,s+1



Tabla 10.11: Par´ametros del esquema de compilaci´on gen´erico de TAG en BU–2SA Para toda transici´on (e, C  F, ) 7−→ (e, G, γ 0 ) y para todo E ∈ P creamos una producci´on hE, Gi[◦◦γ 0 ] → hE, Ci[ ] hC, F i[◦◦] Para toda transici´on (e, C  F, γ) 7−→ (e, G, ) y para todo E ∈ P creamos una producci´on hE, Gi[◦◦] → hE, Ci[ ] hC, F i[◦◦γ] Con respecto al axioma de la gram´atica, tenemos que S = h$0 , $f i. Las derivaciones de la gram´atica lineal de ´ındices obtenida y del aut´omata con dos pilas ascendente cumplen las siguientes propiedades: ∗

∗

hE, Bi[α] ⇒ w, con α 6= , si y s´olo si (w, E, , w) ` (e, E  B, α, ). ∗

∗

hE, Bi[ ] ⇒ w si y s´olo si (m, E, , w) ` (e, E|=m B, |=m , ). La veracidad de estas dos propiedades se demuestra mediante inducci´on mutua en la longitud de las respectivas derivaciones: ∗

Si una derivaci´on (w, E, , w) ` (e, E  B, α, ), con α 6= , es el resultado de aplicar la secuencia t1 , . . . , tm de transiciones en Θ, entonces existe una secuencia p1 , . . . , pm de producciones en P tal que pi es una producci´on creada a partir de ti y la derivaci´on ∗ derecha hE, Bi[α] ⇒ w resultado de aplicar pm , . . . , p1 reconoce w. ∗

Si una derivaci´on (m, E, , w) ` (e, E|=m B, |=m , ) es el resultado de aplicar la secuencia t1 , . . . , tm de transiciones en Θ, entonces existe una secuencia p1 , . . . , pm de producciones en P tal que pi es una producci´on creada a partir de ti y la derivaci´on derecha ∗ hE, Bi[ ] ⇒ w resultado de aplicar pm , . . . , p1 reconoce w. ∗

Si una derivaci´on derecha hE, Bi[α] ⇒ w, con α 6= , reconoce la cadena w como resultado de aplicar la secuencia p1 , . . . , pm de producciones en P , entonces existe una secuencia de transiciones t1 , . . . , tm tal que la pi es una producci´on creada a partir de ∗

ti y la derivaci´on (w, E, , w) ` (e, E  B, α, , ) es el resultado de aplicar la secuencia de transiciones tm , . . . , t1 . ∗

Si una derivaci´on derecha hE, Bi[ ] ⇒ w reconoce la cadena w como resultado de aplicar la secuencia p1 , . . . , pm de producciones en P , entonces existe una secuencia de transiciones t1 , . . . , tm tal que la pi es una producci´on creada a partir de ti y la ∗

derivaci´on (m, E, , w) ` (e, E|=m B, |=m , ) es el resultado de aplicar la secuencia de transiciones tm , . . . , t1 .

2

372

Aut´ omatas con dos pilas

Ejemplo 10.2 El aut´omata con dos pilas ascendente de la tabla 10.12 acepta el lenguaje {an bn cn dn | n > 0}. En la tabla 10.13 se muestra la derivaci´on para la cadena de entrada aaabbbcccddd en dicho aut´omata. La primera columna indica la transici´on aplicada, la segunda se˜ nala el modo del aut´omata en ese momento, la tercera muestra el contenido de la pila maestra, la cuarta muestra el contenido de la pila auxiliar y la quinta muestra la parte de la cadena de entrada que resta por leer. Resulta interesante comparar este aut´omata con el aut´omata con dos pilas fuertemente dirigido definido en la tabla 10.1. Denotaremos por |X| el n´ umero de elementos X apilados en la pila maestra. En el caso del SD–2SA de la tabla 10.1 se comprueba que |A| = |B| durante el modo de escritura mediante la manipulaci´on de los elementos γ almacenados en la pila auxiliar. En el modo de borrado, las transiciones que extra´ıan elementos de la pila maestra se encargaban de comprobar que |B| = |C| y que |A| = |D| al tiempo que mediante la manipulaci´on de los elementos η en la pila se comprobaba que |C| = |D|. En el caso del BU–2SA de la tabla 10.12 no se realiza la comprobaci´on de que |A| = |B| durante el modo de escritura. Sin embargo, durante el modo de borrado se comprueba que |B| = |C|, |A| = |D| y |C| = |D| y en tal caso, por transitividad, se cumple que |A| = |B|. En el caso del SD–2SA de la tabla 10.1, la comprobaci´on de que |A| = |B| durante el modo de llamada le permite mantener la propiedad del prefijo v´alido. En cambio, el BU–2SA de la tabla 10.12 no garantiza dicha propiedad puesto que la no gramaticalidad de la cadena de entrada aabbbcccddd s´olo puede determinarse despu´es de leer aabbbcccdd, que no es prefijo de ninguna cadena v´alida del lenguaje aceptado por el aut´omata, y detectar que |A| 6= |D|. En la tabla 10.14 se muestran las producciones de la gram´atica lineal de ´ındices obtenida a partir de las transiciones del aut´omata con dos pilas ascendente. Utilizamos Γ para representar cualquier s´ımbolo de pila. La derivaci´on de la cadena aaabbbcccddd con esta gram´atica se muestra en la tabla 10.15, en la cual la primera columna indica la producci´on aplicada. ¶

10.4.4.

Tabulaci´ on

Las derivaciones de los aut´omatas con dos pilas ascendentes se pueden clasificar en los tres tipos siguientes: Derivaciones de llamada. Son aquellas que dependen u ´nicamente de la cima de la pila maestra ya que la sesi´on en la cima de la pila auxiliar est´a vac´ıa. Presentan la forma: 0

∗

0

(w, ΞB, ξ|=m , ai . . . an ) ` (m, ΞB  C, ξ|=m , aj . . . an ) donde w ≤ m y tanto B como C pertenecen a la misma sesi´on. En la derivaci´on, se puede consultar B pero no se permite la consulta ni la alteraci´on de Ξ y ξ. En la figura 10.4 se muestra una representaci´on gr´afica de este tipo de derivaciones 2 . Para cualquier Ξ0 ∈ (D0 VS )∗ y ξ 0 ∈ (|=x VI∗ )∗ tal que x ∈ {w, e} y el n´ umero de sesiones en Ξ0 y ξ 0 coincide, se cumple 0

∗

0

(w, Ξ0 B, ξ 0 |=m , ai . . . an ) ` (m, Ξ0 B  C, ξ 0 |=m , aj . . . an ) 2

Puesto que m no es necesariamente w, este tipo de derivaciones pueden extenderse m´ as all´ a del modo de escritura y por tanto la denominaci´ on de derivaciones de llamada puede parecer contraproducente. Sin embargo, con el fin de mantener la homogeneidad con el resto de los modelos de aut´ omata, hemos optado por mantener tal denominaci´ on.

10.4 Aut´ omatas con dos pilas ascendentes

373

(a) (b) (c)

(w, $0 , ) 7−→ (w, $0 |=w A, |=w ) a (w, A, ) 7−→ (w, A0 , ) (w, A0 , ) 7−→ (w, A0  A, )

(d) (e)

(w, A0 , ) 7−→ (w, B 0 , ) (w, B 0 , ) 7−→ (w, B 0  B, )

(f ) (g) (h) (i)

(w, B, ) 7−→ (w, B 0 , ) c (w, B 0 , |=m ) 7−→ (e, C 0 , |=m ) (e, B 0  C 0 , ) 7−→ (e, C, η) c (e, C, ) 7−→ (e, C 0 , )

(j) (k)

(e, C 0 , ) 7−→ (e, D 0 , ) (e, A0  D0 ) 7−→ (e, D, )

b

b

d

d

(l) (e, D, ) 7−→ (e, D 0 , ) (m) (e, D 0 , ) 7−→ (e, $f , ) Tabla 10.12: Transiciones del BU–2SA que acepta {an bn cn dn | n > 0}

w (a) w (b) w (c) w (b) w (c) w (b) w (d) w (e) w (f ) w (e) w (f ) w (g) e (h) e (i) e (h) e (i) e (j) e (k) e (l) e (k) e (l) e (m) e

|=w $0 |=w $0 |=w $0 |=w $0 |=w $0 |=w $0 |=w $0 |=w $0 |=w $0 |=w $0 |=w $0 |=w $0 |=w $0 |=w $0 |=w $0 |=w $0 |=w $0 |=w $0 |=w $0 |=w $0 |=w $0 |=w $0 |=w $0

|=w A |=w A0 |=w A0 |=w A0 |=w A0 |=w A0 |=w A0 |=w A0 |=w A0 |=w A0 |=w A0 |=w A0 |=w A0 |=w A0 |=w A0 |=w A0 |=w A0 |=w A0 |=w A0 |=w D |=w D0 |=w $ f

A  A0  A0  A0  A0  A0  A0  A0  A0  A0  A0  A0  A0  A0  A0 D  D0

A  A0  B0  B0  B0  B0  B0  B0  B0  B0 C  C0  D0

B  B0  B0  B  B0  B0  B0  C 0 C  C0

|=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w |=w

aaabbbcccddd aaabbbcccddd aabbbcccddd aabbbcccddd abbbcccddd abbbcccddd bbbcccddd bbcccddd bbcccddd bcccddd bcccddd cccddd ccddd η ccddd η cddd ηη cddd ηη ddd ηη dd η dd η d d

Tabla 10.13: Configuraciones del BU–2SA para la cadena de entrada aaabbbcccddd

374

Aut´ omatas con dos pilas

(a)

h$0 , Ai[ ] → 

(b)

hΓ, A0 i[◦◦] → hΓ, Ai[◦◦] a

(c)

hA0 , Ai[ ] → 

(d)

hΓ, B 0 i[◦◦] → hΓ, A0 i[◦◦] b

(e)

hB 0 , Bi[ ] → 

(f )

hΓ, B 0 i[◦◦] → hΓ, Bi[◦◦] b

(g)

hΓ, C 0 i[◦◦] → hΓ, B 0 i[◦◦] c

(h)

hΓ, Ci[◦◦η] → hΓ, B 0 i[ ] hB 0 , C 0 i[◦◦]

(i)

hΓ, C 0 i[◦◦] → hΓ, Ci[◦◦] c

(j)

hΓ, D 0 i[◦◦] → hΓ, C 0 i[◦◦] d

(k)

hΓ, Di[◦◦] → hΓ, A0 i[ ] hA0 , D0 i[◦◦]

(l)

hΓ, D 0 i[◦◦] → hΓ, Di[◦◦] d

(m)

hΓ, $f i[◦◦] → hΓ, D 0 i[◦◦]

Tabla 10.14: Producciones de la LIG obtenida a partir del BU–2SA h$0 , $f i[ ] (m)

⇒

h$0 , D0 i[ ]

(l)

⇒

h$0 , Di[ ] d

(k)

⇒

h$0 , A0 i[ ] hA0 , D0 i[ ] d

(l)

⇒

h$0 , A0 i[ ] hA0 , Di[ ] dd

(k)

⇒

h$0 , A0 i[ ] hA0 , A0 i[ ] hA0 , D0 i[ ] dd

(j)

⇒

h$0 , A0 i[ ] hA0 , A0 i[ ] hA0 , C 0 i[ ] ddd

(i)

⇒

h$0 , A0 i[ ] hA0 , A0 i[ ] hA0 , Ci[ ] cddd

(h)

⇒

h$0 , A0 i[ ] hA0 , A0 i[ ] hA0 , B 0 i[ ] hB 0 , C 0 i[ ] cddd

(i)

⇒

h$0 , A0 i[ ] hA0 , A0 i[ ] hA0 , B 0 i[ ] hB 0 , Ci[ ] ccddd

(h)

⇒

h$0 , A0 i[ ] hA0 , A0 i[ ] hA0 , B 0 i[ ] hB 0 , B 0 i[ ] hB 0 , C 0 i[ ] ccddd

(g)

⇒

h$0 , A0 i[ ] hA0 , A0 i[ ] hA0 , B 0 i[ ] hB 0 , B 0 i[ ] hB 0 , B 0 i[ ] cccddd

(f )

⇒

h$0 , A0 i[ ] hA0 , A0 i[ ] hA0 , B 0 i[ ] hB 0 , B 0 i[ ] hB 0 , Bi[ ] bcccddd

(e)

⇒

h$0 , A0 i[ ] hA0 , A0 i[ ] hA0 , B 0 i[ ] hB 0 , B 0 i[ ] bcccddd

(f )

⇒

h$0 , A0 i[ ] hA0 , A0 i[ ] hA0 , B 0 i[ ] hB 0 , Bi[ ] bbcccddd

(e)

⇒

h$0 , A0 i[ ] hA0 , A0 i[ ] hA0 , B 0 i[ ] bbcccddd

(d)

⇒

h$0 , A0 i[ ] hA0 , A0 i[ ] hA0 , A0 i[ ] bbbcccddd

(b)

⇒

h$0 , A0 i[ ] hA0 , A0 i[ ] hA0 , Ai[ ] abbbcccddd

(c)

⇒

h$0 , A0 i[ ] hA0 , A0 i[ ] abbbcccddd

(b)

⇒

h$0 , A0 i[ ] hA0 , Ai[ ] aabbbcccddd

(c)

⇒

h$0 , A0 i[ ] aabbbcccddd

(b)

⇒

h$0 , Ai[ ] aaabbbcccddd

(a)

⇒

aaabbbcccddd

Tabla 10.15: Derivaci´on en LIG de la cadena aaabbbcccddd

10.4 Aut´ omatas con dos pilas ascendentes

375

m C w B

m’

m’ ξ

B

ξ i

j

Figura 10.4: Derivaciones de llamada en BU-2SA por lo que este tipo de derivaciones puede ser representado de manera compacta por los correspondientes ´ıtems de la forma 0

[B, i, C, j, |=m | −, −, −, −, −]m Derivaciones de retorno. Son aquellas que se inician en una sesi´on en modo de escritura y terminan en la misma sesi´on en modo de borrado con una sesi´on no vac´ıa en la cima de la pila auxiliar. Presentan la forma ∗

(w, ΞB, ξ|=m , ai . . . an ) `d1 (w, ΞB Ξ1 D, ξ|=m , ap . . . an ) ∗

`d2 (e, ΞB Ξ1 D  E, ξ|=m φ, aq . . . an ) ∗

`d3 (e, ΞB ⊗ C, ξ|=m φη, aj . . . an ) donde ⊗ ∈ D 0 , φ ∈ VI∗ , η ∈ VI y tanto B como D, E y C pertenecen a la misma sesi´on. La subderivaci´on d1 puede consultar B pero no puede consultar ni alterar Ξ y ξ. La subderivaci´on d2 puede consultar D pero no puede consultar ni alterar ΞB Ξ1 ni ξ. Finalmente, la pila ξ|=m es la misma en toda la derivaci´on. Es importante se˜ nalar que si ⊗ = |=m , entonces la derivaci´on no puede conducir a la aceptaci´on de la cadena de entrada puesto que no es posible eliminar φ de la pila auxiliar. Sin embargo, tal tipo de derivaciones puede obtenerse y por tanto es necesario considerarlas. En la figura 10.5 se muestra una representaci´on gr´afica de este tipo de derivaciones. umero de sesiones en Para cualquier Ξ0 ∈ (D0 VS )∗ y ξ 0 ∈ (|=x VI∗ )∗ tal que x ∈ {w, e}, el n´ Ξ0 y ξ 0 coincide y existe una derivaci´on ∗

(w, D, ξ|=m , ap . . . an ) ` (e, D  E, ξ|=m φ, aq . . . an ) se cumple que ∗

(w, Ξ0 B, ξ 0 |=m , ai . . . an ) `d1 (w, Ξ0 B Ξ1 D, ξ 0 |=m , ap . . . an ) ∗

`d2 (e, Ξ0 B Ξ1 D  E, ξ 0 |=m φ, aq . . . an ) ∗

`d3 (e, Ξ0 B ⊗ C, ξ 0 |=m φη, aj . . . an ) Ello posibilita que las derivaciones de retorno puedan ser representadas por ´ıtems de la forma [B, i, ⊗C, j, η | D, p, |=m , E, q]e

376

Aut´ omatas con dos pilas

e E w D

m

φ m

D

ξ

ξ

η

e C w B

m

B

B

φ m

B

ξ

ξ

i

p

q

j

Figura 10.5: Derivaciones de retorno en BU-2SA m m’

ξ

B

m’

C m’

ξ

B

i

j

Figura 10.6: Derivaciones de puntos especiales en BU-2SA Derivaciones de puntos especiales. Son aquellas derivaciones que finalizan en una sesi´on m´ınima, con un u ´nico elemento el la pila maestra y ninguna en la auxiliar. Estas configuraciones se tienen t´ıpicamente cuando se acaba de crear una nueva sesi´on y cuando se est´a a punto de finalizar una sesi´on. Presentan la forma ∗

0

0

(m0 , ΞB, ξ, ai . . . an ) ` (m, ΞB|=m C, ξ|=m , aj . . . an ) Este tipo de derivaciones se muestra gr´aficamente en la figura 10.6. Para cualquier Ξ0 ∈ (D0 VS )∗ y ξ 0 ∈ (|=x VI∗ )∗ tal que x ∈ {w, e} y el n´ umero de sesiones en 0 0 Ξ y ξ coincide, se cumple ∗

0

0

(m0 , Ξ0 B, ξ 0 , ai . . . an ) ` (m, Ξ0 B|=m C, ξ 0 |=m , aj . . . an ) por lo que podemos utilizar ´ıtems de la siguientes formas para representar este tipo de derivaciones: 0 0 [B, i, |=m C, j, |=m | −, −, −, −, −]m Los ´ıtems se combinan mediante las reglas descritas en la tabla 10.16, a partir del ´ıtem inicial [−, −, |=w $ , 0, |=w | −, −, −, −, −]w 0

La aceptaci´on de la cadena se entrada a1 . . . an se indica mediante la presencia de ´ıtems de la forma [$0 , 0, |=w $f , n, |=w | −, −, −, −, −]e

10.4 Aut´ omatas con dos pilas ascendentes

0

[B, i, ⊗C, j, η | D, p, |=m , E, q]m [B, i, ⊗F, k, η | D, p, |=m0 , E, q]m

377

a

(m, C, ) 7−→ (m, F, ), k = j si a = , k = j + 1 si a ∈ VT

0

[B, i, ⊗C, j, η | D, p, |=m , E, q]m (m, C, ) 7−→ (w, C|=m F, |=m ) [C, j, |=m F, j, |=m | −, −, −, −, −]w [B, i, ⊗C, j, |=m | −, −, −, −, −]w (w, C, ) 7−→ (w, C  F, ) [C, j, F, j, |=m | −, −, −, −, −]w [B, i, ⊗C, j, |=m | −, −, −, −, −]w [B, i, ⊗F, k, |=m | −, −, −, −, −]e

a

(w, C, |=m ) 7−→ (e, F, |=m ), k = j si a = , k = j + 1 si a ∈ VT

[C, j, |=m F, k, |=m | −, −, −, −, −]e 0 [B, i, ⊗C, j, η | D, p, |=m , E, q]m [B, i, ⊗G, k, η | D, p, |=m0 , E, q]m [C, j, F, k, η | D, p, |=m , E, q]e [B, i, ⊗C, j, |=m | −, −, −, −, −]w [B, i, ⊗G, k, η | D, p, |=m , E, q]e [C, j, F, k, η 0 | D, p, |=m , E, q]e [B, i, ⊗1 C, j, |=m | −, −, −, −, −]w [D, p, ⊗2 E, q, η | O, u, |=m , P, v]e [B, i, ⊗1 G, k, η | O, u, |=m , P, v]e [C, j, F, k, η 0 | D, p, |=m , E, q]e [B, i, ⊗C, j, |=m | −, −, −, −, −]w [B, i, ⊗G, k, η | C, j, |=m , F, k]e

(e, C|=m F, |=m ) 7−→ (m, G, )

(e, C  F, ) 7−→ (e, G, )

(e, C  F, η 0 ) 7−→ (e, G, )

(e, C  F, ) 7−→ (e, G, η)

Tabla 10.16: Reglas de combinaci´on de ´ıtems en BU-2SA Teorema 10.8 La manipulaci´ on de configuraciones mediante la aplicaci´ on de transiciones en los aut´ omatas con dos pilas ascendentes es equivalente a la manipulaci´ on de ´ıtems mediante las reglas de combinaci´ on de la tabla 10.16. Demostraci´on: Mostraremos que para toda derivaci´on existe una regla de combinaci´on que produce un ´ıtem que representa de forma compacta dicha derivaci´on y que toda regla de combinaci´on se corresponde con una derivaci´on v´alida del aut´omata. Para ello detallaremos todas las posibles derivaciones, junto con las reglas de combinaci´on ´ıtems correspondientes, en la siguiente lista. a

Derivaciones que son el resultado de aplicar una transici´on (m, C, ) 7−→ (m, F, )

378

Aut´ omatas con dos pilas • a una derivaci´on de llamada: ∗

0

0

` (m, ΞB  C, ξ|=m , aj . . . an ) 0 ` (m, ΞB  F, ξ|=m , ak . . . an )

(w, ΞB, ξ|=m , ai . . . an )

0

[B, i, C, j, |=m | −, −, −, −, −]m [B, i, F, k, |=m0 | −, −, −, −, −]m

a

(m, C, ) 7−→ (m, F, )

• a una derivaci´on de retorno: ∗

(w, ΞB, ξ|=m , ai . . . an )

` (w, ΞB Ξ1 D, ξ|=m , ap . . . an ) ∗

` (e, ΞB Ξ1 D  E, ξ|=m φ, aq . . . an ) ∗

` (e, ΞB ⊗ C, ξ|=m φη, aj . . . an ) ` (e, ΞB ⊗ F, ξ|=m φη, ak . . . an ) [B, i, ⊗C, j, η | D, p, |=m , E, q]e [B, i, ⊗F, k, η | D, p, |=m , E, q]e

a

(e, C, ) 7−→ (e, F, )

• a una derivaci´on de puntos especiales: ∗

(m0 , ΞB, ξ, ai . . . an )

0

0

0

` (m, ΞB|=m C, ξ|=m , aj . . . an ) 0 0 ` (m, ΞB|=m F, ξ|=m , ak . . . an )

0

[B, i, |=m C, j, |=m | −, −, −, −, −]m [B, i, |=m0 F, k, |=m0 | −, −, −, −, −]m

a

(m, C, ) 7−→ (m, F, )

donde k = j si a =  y k = j + 1 si a ∈ VT : Derivaciones que son el resultado (m, C, ) 7−→ (w, C|=m F, |=m )

de

aplicar

una

transici´on

de

• a una derivaci´on de llamada: ∗

0

(w, ΞB, ξ|=m , ai . . . an )

0

` (m, ΞB  C, ξ|=m , aj . . . an ) 0 ` (w, ΞB  C|=m F, ξ|=m |=m , aj . . . an )

0

[B, i, C, j, |=m | −, −, −, −, −]m (m, C, ) 7−→ (w, C|=m F, |=m ) [C, j, |=m F, j, |=m | −, −, −, −, −]w • a una derivaci´on de retorno: ∗

0

(w, ΞB, ξ|=m , ai . . . an )

0

` (w, ΞB Ξ1 D, ξ|=m , ap . . . an ) ∗

0

` (e, ΞB Ξ1 D  E, ξ|=m φ, aq . . . an ) ∗

0

` (e, ΞB ⊗ C, ξ|=m φη, aj . . . an ) 0 ` (w, ΞB ⊗ C|=e F, ξ|=m φη|=e , aj . . . an ) 0

[B, i, ⊗C, j, η | D, p, |=m , E, q]e (e, C, ) 7−→ (w, C|=e F, |=e ) [C, j, |=e F, j, |=e | −, −, −, −, −]w • a una derivaci´on de puntos especiales: (m0 , ΞB, ξ, ai . . . an )

0

0

∗

0

0

` (m, ΞB|=m C, ξ|=m , aj . . . an ) 0 0 ` (w, ΞB|=m C|=m F, ξ|=m |=m , aj . . . an )

[B, i, |=m C, j, |=m | −, −, −, −, −]m (m, C, ) 7−→ (w, C|=m F, |=m ) [C, j, |=m F, j, |=m | −, −, −, −, −]w

tipo

10.4 Aut´ omatas con dos pilas ascendentes Derivaciones que son el (w, C, ) 7−→ (w, C  F, )

379

resultado

de

aplicar

una

transici´on

de

tipo

• a una derivaci´on de llamada: ∗

(w, ΞB, ξ|=m , ai . . . an )

` (w, ΞB  C, ξ|=m , aj . . . an ) ` (w, ΞB  C  F, ξ|=m , aj . . . an )

[B, i, C, j, |=m | −, −, −, −, −]w (w, C, ) 7−→ (w, C  F, ) [C, j, F, j, |=m | −, −, −, −, −]w • a una derivaci´on de puntos especiales: ∗

` (w, ΞB|=m C, ξ|=m , aj . . . an ) ` (w, ΞB|=m C  F, ξ|=m , aj . . . an )

(m, ΞB, ξ, ai . . . an )

[B, i, |=m C, j, |=m | −, −, −, −, −]w (w, C, ) 7−→ (w, C  F, ) [C, j, F, j, |=m | −, −, −, −, −]w Derivaciones que son el resultado de aplicar una transici´on de a (w, C, |=m ) 7−→ (e, F, |=m )

tipo

• a una derivaci´on de llamada: ∗

(w, ΞB, ξ|=m , ai . . . an )

` (w, ΞB  C, ξ|=m , aj . . . an ) ` (e, ΞB  F, ξ|=m , ak . . . an )

[B, i, C, j, |=m | −, −, −, −, −]w [B, i, F, k, |=m | −, −, −, −, −]e • a una derivaci´on de puntos especiales: (m, ΞB, ξ, ai . . . an )

a

(w, C, |=m ) 7−→ (e, F, |=m )

∗

` (w, ΞB|=m C, ξ|=m , aj . . . an ) ` (e, ΞB|=m F, ξ|=m , ak . . . an )

[B, i, |=m C, j, |=m | −, −, −, −, −]w a (w, C, |=m ) 7−→ (e, F, |=m ) [B, i, |=m F, k, |=m | −, −, −, −, −]e donde k = j si a =  y k = j + 1 si a ∈ VT : Derivaciones que son el resultado de aplicar una transici´on de tipo (e, C|=m F, |=m ) 7−→ (m, G, ) a una derivaci´on obtenida tras aplicar una transici´on (m, C, ) 7−→ (w, C|=m F 0 , |=m ) • a una derivaci´on de llamada: 0

(w, ΞB, ξ|=m , ai . . . an )

∗

0

` (m, ΞB  C, ξ|=m , aj . . . an ) 0 ` (w, ΞB  C|=m F 0 , ξ|=m |=m , aj . . . an ) ∗

0

` (e, ΞB  C|=m F, ξ|=m |=m , ak . . . an ) 0 ` (m, ΞB  G, ξ|=m , ak . . . an ) [C, j, |=m F, k, |=m | −, −, −, −, −]e 0 [B, i, C, j, |=m | −, −, −, −, −]m [B, i, G, k, |=m0 | −, −, −, −, −]m • a una derivaci´on de retorno: 0

(w, ΞB, ξ|=m , ai . . . an )

(e, C|=w F, |=w ) 7−→ (w, G, )

∗

0

` (w, ΞB Ξ1 D, ξ|=m , ap . . . an ) ∗

0

` (e, ΞB Ξ1 D  E, ξ|=m φ, aq . . . an ) ∗

0

` (e, ΞB ⊗ C, ξ|=m φη, aj . . . an ) 0 ` (w, ΞB ⊗ C|=e F 0 , ξ|=m φη|=e , aj . . . an ) ∗ 0 ` (e, ΞB ⊗ C|=e F, ξ|=m φη|=e , a . . . a ) k

0

` (e, ΞB ⊗ G, ξ|=m φη, ak . . . an )

n

380

Aut´ omatas con dos pilas [C, j, |=e F, k, |=e | −, −, −, −, −]e 0 [B, i, ⊗C, j, η | D, p, |=m , E, q]e [B, i, ⊗G, k, η | D, p, |=m0 , E, q]e • a una derivaci´on de puntos especiales: (m0 , ΞB, ξ, ai . . . an )

(e, C|=e F, |=e ) 7−→ (e, G, )

∗

0

0

` (m, ΞB|=m C, ξ|=m , aj . . . an ) 0 0 ` (w, ΞB|=m C|=m F 0 , ξ|=m |=m , aj . . . an ) ∗

0

0

` (e, ΞB|=m C|=m F, ξ|=m |=m , ak . . . an ) 0 0 ` (m, ΞB|=m G, ξ|=m , ak . . . an ) [C, j, |=m F, k, |=m | −, −, −, −, −]e 0 0 [B, i, |=m C, j, |=m | −, −, −, −, −]m (e, C|=m F, |=m ) 7−→ (m, G, ) [B, i, |=m0 G, k, |=m0 | −, −, −, −, −]m Derivaciones que son el resultado de aplicar una transici´on de tipo (e, C  F, ) 7−→ (e, G, ) a una derivaci´on obtenida tras aplicar una transici´on (w, C, ) 7−→ (w, C  F 0 , ) • a una derivaci´on de llamada: (w, ΞB, ξ|=m , ai . . . an )

∗

` (w, ΞB  C, ξ|=m , aj . . . an ) ` (w, ΞB  C  F 0 , ξ|=m , aj . . . an ) ∗

` (w, ΞB  C  F 0 Ξ1 D, ξ|=m , ap . . . an ) ∗

` (e, ΞB  C  F 0 Ξ1 D  E, ξ|=m φ, aq . . . an ) ∗

` (e, ΞB  C  F, ξ|=m φη, ak . . . an ) ` (e, ΞB  G, ξ|=m φη, ak . . . an ) [C, j, F, k, η | D, p, |=m , E, q]e [B, i, C, j, |=m | −, −, −, −, −]w [B, i, G, k, η | D, p, |=m , E, q]e

(e, C  F, ) 7−→ (e, G, )

• a una derivaci´on de puntos especiales: (m, ΞB, ξ, ai . . . an )

∗

` (w, ΞB|=m C, ξ|=m , aj . . . an ) ` (w, ΞB|=m C  F 0 , ξ|=m , aj . . . an ) ∗

` (e, ΞB|=m C  F, ξ|=m , ak . . . an ) ` (e, ΞB|=m G, ξ|=m , ak . . . an ) [C, j, F, k, |=m | −, −, −, −, −]e [B, i, |=m C, j, |=m | −, −, −, −, −]w (e, C  F, ) 7−→ (e, G, ) [B, i, |=m G, k, |=m | −, −, −, −, −]e Derivaciones que son el resultado de aplicar una transici´on de tipo (e, C  F, η 0 ) 7−→ (e, G, ) a una derivaci´on obtenida tras aplicar una transici´on (w, C, ) 7−→ (w, C  F 0 , ) • a una derivaci´on de llamada, con los dos casos siguientes: (w, ΞB, ξ|=m , ai . . . an )

∗

` (w, ΞB  C, ξ|=m , aj . . . an ) ` (w, ΞB  C  F 0 , ξ|=m , aj . . . an ) ∗

` (w, ΞB  C  F 0 Ξ1 D, ξ|=m , ap . . . an ) ∗

` (w, ΞB  C  F 0 Ξ1 D Ξ2 O, ξ|=m , au . . . an ) ∗

` (e, ΞB  C  F 0 Ξ1 D Ξ2 O  P, ξ|=m φη, au . . . an ) ∗

` (e, ΞB  C  F 0 Ξ1 D  E, ξ|=m φη, aq . . . an ) ∗

` (e, ΞB  C  F, ξ|=m φηη 0 , ak . . . an ) ` (e, ΞB  G, ξ|=m φη, ak . . . an )

10.4 Aut´ omatas con dos pilas ascendentes [C, j, F, k, η 0 | D, p, |=m , E, q]e [B, i, C, j, |=m | −, −, −, −, −]w [D, p, E, q, η | O, u, |=m , P, v]e [B, i, G, k, η | O, u, |=m , P, v]e (w, ΞB, ξ|=m , ai . . . an )

381

(e, C  F, η 0 ) 7−→ (e, G, )

∗

` (w, ΞB  C, ξ|=m , aj . . . an ) ` (w, ΞB  C  F 0 , ξ|=m , aj . . . an ) ∗

` (w, ΞB  C  F 0 ΞD, ξ|=m , ap . . . an ) ∗

` (e, ΞB  C  F 0 ΞD  E, ξ|=m , aq . . . an ) ∗

` (e, ΞB  C  F, ξ|=m η 0 , ak . . . an ) ` (e, ΞB  G, ξ|=m , ak . . . an ) [C, j, F, k, η 0 | D, p, |=m , E, q]e [B, i, C, j, |=m | −, −, −, −, −]w [D, p, E, q, |=m | −, −, −, −, −]e [B, i, G, k, |=m | −, −, −, −, −]e

(e, C  F, η 0 ) 7−→ (e, G, )

• a una derivaci´on de puntos especiales, con los dos casos siguientes: ∗

` (w, ΞB|=m C, ξ|=m , aj . . . an ) ` (w, ΞB|=m C  F 0 , ξ|=m , aj . . . an )

(m, ΞB, ξ, ai . . . an )

∗

` (w, ΞB|=m C  F 0 Ξ1 D, ξ|=m , ap . . . an ) ∗

` (e, ΞB|=m C  F 0 Ξ1 D  E, ξ|=m , aq . . . an ) ∗

` (e, ΞB|=m C  F, ξ|=m η 0 , ak . . . an ) ` (e, ΞB|=m G, ξ|=m , ak . . . an ) [C, j, F, k, η 0 | D, p, |=m , E, q]e [B, i, |=m C, j, |=m | −, −, −, −, −]w [D, p, E, q, η | −, −, −, −, −]e [B, i, |=m G, k, η | −, −, −, −, −]e (m, ΞB, ξ, ai . . . an )

(e, C  F, η 0 ) 7−→ (e, G, )

∗

` (w, ΞB|=m C, ξ|=m , aj . . . an ) ` (w, ΞB|=m C  F 0 , ξ|=m , aj . . . an ) ∗

` (w, ΞB|=m C  F 0 Ξ1 D, ξ|=m , ap . . . an ) ∗

` (w, ΞB|=m C  F 0 Ξ1 D ΞO, ξ|=m , au . . . an ) ∗

` (e, ΞB|=m C  F 0 Ξ1 D ΞO  P, ξ|=m φ, av . . . an ) ∗

` (e, ΞB|=m C  F 0 Ξ1 D  E, ξ|=m φη, aq . . . an ) ∗

` (e, ΞB|=m C  F, ξ|=m φηη 0 , ak . . . an ) ` (e, ΞB|=m G, ξ|=m φη, ak . . . an ) [C, j, F, k, η 0 | D, p, |=m , E, q]e [B, i, |=m C, j, |=m | −, −, −, −, −]w [D, p, E, q, η | O, u, |=m , P, v]e [B, i, |=m G, k, η | O, u, |=m , P, v]e

(e, C  F, η 0 ) 7−→ (e, G, )

En este caso la configuraci´on resultante no puede conducir a una configuraci´on final porque la pila auxiliar contiene en su cima una sesi´on no vac´ıa que es imposible eliminar. Derivaciones que son el resultado de aplicar una transici´on de tipo (e, C  F, ) 7−→ (e, G, η) a una derivaci´on obtenida tras aplicar una transici´on (w, C, ) 7−→ (w, C  F 0 , )

382

Aut´ omatas con dos pilas • a una derivaci´on de llamada, con los dos casos siguientes: ∗

(w, ΞB, ξ|=m , ai . . . an )

` (w, ΞB  C, ξ|=m , aj . . . an ) ` (w, ΞB  C  F 0 , ξ|=m , aj . . . an ) ∗

` (w, ΞB  C  F 0 Ξ1 D, ξ|=m , ap . . . an ) ∗

` (e, ΞB  C  F 0 Ξ1 D  E, ξ|=m φ, aq . . . an ) ∗

` (e, ΞB  C  F, ξ|=m φη 0 , ak . . . an ) ` (e, ΞB  G, ξ|=m φη 0 η, ak . . . an ) [C, j, F, k, η 0 | D, p, |=m , E, q]e [B, i, C, j, |=m | −, −, −, −, −]w [B, i, G, k, η | C, j, |=m , F, k]e

(e, C  F, ) 7−→ (e, G, η)

∗

(w, ΞB, ξ|=m , ai . . . an )

` (w, ΞB  C, ξ|=m , aj . . . an ) ` (w, ΞB  C  F 0 , ξ|=m , aj . . . an ) ∗

` (e, ΞB  C  F, ξ|=m , ak . . . an ) ` (e, ΞB  G, ξ|=m η, ak . . . an ) [C, j, F, k, |=m | −, −, −, −, −]e [B, i, C, j, |=m | −, −, −, −, −]w [B, i, G, k, η | C, j, |=m , F, k]e

(e, C  F, ) 7−→ (e, G, η)

• a una derivaci´on de puntos especiales, con los dos casos siguientes: (m, ΞB, ξ, ai . . . an )

∗

` (w, ΞB|=m C, ξ|=m , aj . . . an ) ` (w, ΞB|=m C  F 0 , ξ|=m , aj . . . an ) ∗

` (w, ΞB|=m C  F 0 Ξ1 D, ξ|=m , ap . . . an ) ∗

` (e, ΞB|=m C  F 0 Ξ1 D  E, ξ|=m φ, aq . . . an ) ∗

` (e, ΞB|=m C  F, ξ|=m φη 0 , ak . . . an ) ` (e, ΞB|=m G, ξ|=m φη 0 η, ak . . . an ) [C, j, F, k, η 0 | D, p, |=m , E, q]e [B, i, |=m C, j, |=m | −, −, −, −, −]w [B, i, |=m G, k, η | C, j, |=m , F, k]e (m, ΞB, ξ, ai . . . an )

(e, C  F, ) 7−→ (e, G, η)

∗

` (w, ΞB|=m C, ξ|=m , aj . . . an ) ` (w, ΞB|=m C  F 0 , ξ|=m , aj . . . an ) ∗

` (e, ΞB|=m C  F, ξ|=m , ak . . . an ) ` (e, ΞB|=m G, ξ|=m η, ak . . . an ) [C, j, F, k, |=m | −, −, −, −, −]e [B, i, |=m C, j, |=m | −, −, −, −, −]w [B, i, |=m G, k, η | C, j, |=m , F, k]e

(e, C  F, ) 7−→ (e, G, η)

En ambos casos, las configuraciones resultantes no pueden llevar al aut´omata a una configuraci´on final puesto que al ser la forma de la pila principal ΞB|=m G y no estar vac´ıa la sesi´on situada en la cima de la pila auxiliar, es imposible vaciar esta u ´ltima. A partir de esta lista se puede mostrar por inducci´on en la longitud de las derivaciones que tanto mediante la manipulaci´on de configuraciones como mediante la manipulaci´on de ´ıtems se obtienen los mismos resultados. 2

10.4 Aut´ omatas con dos pilas ascendentes

383

La complejidad temporal en el peor caso con respecto a la longitud n de la cadena de entrada es O(n6 ) y viene determinada por la regla de combinaci´on de ´ıtems [C, j, F, k, η 0 | D, p, |=m , E, q]e [B, i, ⊗1 C, j, |=m | −, −, −, −, −]w [D, p, ⊗2 E, q, η | O, u, |=m , P, v]e [B, i, ⊗1 G, k, η | O, u, |=m , P, v]e

(e, C  F, η 0 ) 7−→ (e, G, )

que manipula 7 posiciones de la cadena de entrada, aunque s´olo 6 de manera simult´anea. La complejidad temporal con respecto a la cadena de entrada es O(n4 ) puesto que cada ´ıtem almacena 4 posiciones de la cadena de entrada.