Siguiente: Lenguajes libres de contexto Un nivel arriba: Autómatas de pila Anterior: Autómatas de pila deterministas

Autómatas de pila con escritura

Un autómata de pila contiene un arreglo de entrada y una pila. El arreglo de entrada es donde se inscribe la palabra de entrada, y es recorrido, sin retroceso, de izquierda a derecha por el autómata. En este arreglo, el autómata se detiene en su recorrido cuando se encuentra con una transición de la forma (estado, $\mbox{\it nil\/}$,tope_de_la_pila). La pila es un dispositivo de almacenamiento del tipo ``el primero en entrar es el último en salir''. Consideremos ahora un segundo arreglo, llamado de salida, que es donde se inscribirá la palabra de salida y que el autómata recorre, también sin retroceso, de izquierda a derecha. Dada una palabra de entrada $\sigma$, una correspondiente palabra de salida $\tau$ será la que quede inscrita en la cinta tras de que se haya leído toda la palabra $\sigma$ y, además, en esa situación, se hayan agotado todas las transiciones de la forma (estado_actual, $\mbox{\it nil\/}$,tope_de_la_pila). Formalmente: Un autómata de pila con escritura es una estructura de la forma

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

donde

$$\begin{eqnarray*}Q &:& \mbox{\rm es el conjunto de {\em estados},} \\ \mbox{\i... ...\/} &:& \mbox{\rm es el s\'\i mbolo \lq\lq inicial'' para la pila.} \end{eqnarray*}$$

En cada momento, el autómata funciona como sigue: Si se está en el estado $q\in Q$, se recibe el símbolo $e\in\mbox{\it Ent\/}$ y en el tope de la pila se encuentra el símbolo $Y\in\mbox{\it AlfP\/}$,

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

Ejemplo (Transformación de notación de enfijo a notación de sufijo): Las expresiones aritméticas se forman mediante constantes, variables y operadores. Consideremos operadores unarios, $\mbox{\it Oper\/}_1$, y binarios, $\mbox{\it Oper\/}_2$. Supongamos además, como es convencional en cualquier lenguaje de programación de alto nivel y en la notación usual de enfijo, que los operadores unarios tienen prioridad de aplicación sobre los binarios, y que $\mbox{\it Oper\/}_1$ y $\mbox{\it Oper\/}_2$ están jerarquizados internamente por prioridades de aplicación: Un operador con prioridad mayor se aplicará primeramente y operadores con igual prioridad se aplican de derecha a izquierda. Los paréntesis se usan para imponer el orden de aplicación de los operadores pasando por alto las convenciones de prioridades. Sea T₀ el conjunto formado por las constantes y las variables. El conjunto de términos en notación de enfijo, y para cada término su operador principal, se define como sigue:

$$\begin{array}{rlclcl} \mbox{\rm i)} & \xi\in T_0 &\Rightarro... ...{\it OpPrinc\/}((\xi))=\mbox{\it OpPrinc\/}(\xi)] \end{array}$$

La notación de sufijo, o llamada también polaca, compone a los términos de la aritmética en el esquema [Unico_Operando][Operador], en el caso de operadores unarios, o bien [Primer_Operando][Segundo_Operando][Operador], en el caso de operadores binarios. Formalmente, los términos se definen de la siguiente manera:

$$\begin{array}{rlcl} \mbox{\rm i)} & \xi\in T_0 &\Rightarrow&... ...{\it Oper\/}_2 &\Rightarrow& [\xi_1\xi_2 o_2\in T] \end{array}$$

Cada término $\xi$ en notación de enfijo corresponde a uno único equivalente $\mbox{\it Tr\/}(\xi)$ en notación de sufijo. De hecho la especificación de la ``traducción'' Tr queda como sigue:

$$\begin{array}{rlcl} \mbox{\rm i)} & \xi\in T_0 &\Rightarrow&... ...arrow& \mbox{\it Tr\/}((\xi))=\mbox{\it Tr\/}(\xi) \end{array}$$

La transformación Tr puede calcularse mediante un autómata de pila de escritura: En su arreglo de entrada se da una expresión aritmética de enfijo y en su arreglo de salida ha de quedar la expresión de sufijo equivalente. En vez de dar explícitamente la especificación del autómata de pila, bosquejaremos un algoritmo describiendo el funcionamiento del autómata. Para ello, utilizaremos los conceptos siguientes:

escribir:

poner en la posición actual del arreglo de salida al símbolo que se indique, e incrementar la posición actual una posición a la derecha,

empilar:

se coloca el símbolo actual del arreglo de entrada en la pila, es decir ése pasa a ser el contenido del tope de la pila, y se avanza un lugar en la posición actual de la entrada,

desempilar:

se escribe el contenido del tope de la pila en el arreglo de salida, y se le suprime de la pila,

e:

variable que denota al símbolo leído en el arreglo de entrada, en la posición actual,

t:

variable que denota al símbolo leído en el tope de la pila,

Alfabeto de la pila:

Por cada operador unario o binario o utilizaremos dos símbolos o' y o. Ambos ``recuerdan'' que se ha leído el operador o. El primero indica que aún falta por leerse un argumento. También utilizaremos dos paréntesis izquierdos (' y (.

Algoritmo:

1.

Inicialmente, se está en el estado inicial, se está leyendo el extremo izquierdo de la cadena de entrada y en la pila se tiene en su tope al símbolo inicial X. Es decir, e es el primer símbolo de la cadena de entrada y t=X. La cadena de salida está en blanco.

2.

En función del valor de e, procédase según sea el caso:

(a)

e=(: Empílese, en principio, todo paréntesis izquierdo como ('. Si t=o', para algún operador o, entonces sustitúyase o' por su respectivo símbolo o.

(b)

$e\in T_0$ (se lee un factor): Escríbase e. Si t=o', para algún operador o, entonces sustitúyase o' por su respectivo símbolo o. Si t=(' entonces sustitúyase (' por (.

(c)

$e=o_1\in\mbox{\it Oper\/}_1$ (se lee un operador unario): Procédase según el tope de la pila.

i.

Si t=o', para algún operador o, entonces sustitúyase o' por o.

Empílese o₁'.

(d)

$e=o_2\in\mbox{\it Oper\/}_2$: (se lee un operador binario): Procédase según el tope de la pila.

i.

En tanto t=o, para algún operador binario o con $\mbox{\it Prior\/}(o)\geq\mbox{\it Prior\/}(o_2)$: Desempílese o.

ii.

t=o', para algún operador binario o: La cadena de entrada está mal formada. En este caso, termínese el procedimiento.

iii.

t=(': La cadena de entrada está mal formada. En este caso, termínese el procedimiento.

Empílese o₂'.

(e)

e=): Desempílese uno a uno todos los operadores en la pila hasta encontrar ( en el tope de la pila y entonces suprímasele. Si en el transcurso de tal acción apareciese un símbolo primado o bien no apareciese tal ( entonces la cadena de entrada está mal formada. En este caso, termínese el procedimiento.

(f)

$e=\mbox{\it nil\/}$: Desempílese uno a uno todos los operadores en la pila hasta vaciarla, i.e. hasta llegar a X. Si en el transcurso de tal acción apareciese un símbolo primado o bien un paréntesis izquierdo ( entonces la cadena de entrada está mal formada. En este caso, termínese el procedimiento.

En el caso de autómatas de pila con escritura, una descripción instantánea (DI) es una cadena

$$q\sigma;\tau;\omega\in Q\times\mbox{\it Ent\/}^*\times\mbox{\it AlfP\/}^*\times\mbox{\it Sal\/}^*$$

que indica que el autómata está en el estado q, se está leyendo el primer símbolo a la izquierda de $\sigma$, $\tau$ es el contenido de la pila y $\omega$ es la cadena inscrita en la salida. En la figura 5.1 presentamos dos computaciones del autómata arriba descrito para sendas cadenas de entrada. La de la izquierda está bien formada mientras que la de la derecha no lo está. En cada rengón sólo ponemos la pareja $\tau;\omega$, correspondientes a la pila (el tope es su estremo izquierdo) y a la salida de cualquier DI. Cada rengón corresponde a un símbolo leído en la cadena de entrada.

  

Figure 5.1: Conversiones a notación polaca.

Siguiente: Lenguajes libres de contexto Un nivel arriba: Autómatas de pila Anterior: Autómatas de pila deterministas