Automatas de pila Unidad 2

Introducción

De igual manera que los lenguajes regulares se pueden representar mediante autómatas finitos deterministas, los lenguajes independientes del contexto tienen su correspondencia en otro tipo de dispositivo: el Autómata a Pila (AP).

Un autómata a pila es un dispositivo que tiene acceso a:

• Una secuencia de símbolos de entrada, que en general se representa por una cinta que se desplaza frente a un mecanismo de captación de dichos símbolos.

• El símbolo superior de una memoria en pila (LIFO)

Un autómata a pila se encuentra en cada momento en un estado determinado y el estado siguiente depende de los tres elementos siguientes:

•  estado actual
• símbolo de entrada
•  símbolo superior de la pila

Generalmente, el autómata a pila es no determinista en el sentido de que se permite que haya varias acciones posibles en cada momento.

Un AP puede realizar dos tipos de operaciones elementales:

1. Dependientes de la entrada. 

Se lee la cinta y se avanza la cabeza lectora, En función:

• del estado actual (qi)
• del símbolo leído en la cinta (a)
• del símbolo en la cima de la pila (Z)

Se pasa a un nuevo estado, se elimina el elemento Z de la cima de la pila y se introduce en su lugar una cadena de símbolos.

     2. Independientes de la entrada.

Las mismas operaciones que en el caso anterior, sólo que no se lee la cinta, ni se avanza la cabeza lectora. Se maneja la pila sin la información de entrada.

Definición formal de un AP

Un autómata a pila es una séptupla:

AP= (Σ, Γ, Q, A0, q0, f, F)

donde :

1. Σ es el alfabeto de entrada
2. Γ es el alfabeto de la pila
3. Q es un conjunto finito de estados
4. A0 ∈ Γ es el símbolo inicial de la pila
5. q0 ∈ Q el estado inicial del autómata
6. F ⊆ Q es el subconjunto de estados finales
7. f es una aplicación denominada función de transición de ternas (estado, símbolo de entrada o λ, símbolo de pila) en el conjunto de las partes Q×Γ*

f : Q×{Σ∪{λ}}× Γ → 2 Q×Γ* (subconjunto finito)

Un AP comienza su funcionamiento en la configuración inicial:

•  en el estado inicial (q0)
• con sólo un símbolo en la pila (A0)
• con la cabeza lectora en el primer símbolo de la entrada

 A partir de esta configuración realiza transiciones según la definición de la función f.

Interpretación de la función de transición

Representaremos con:

(a, b,...) los elementos de Σ

 (A, B, C..) los de Γ

(x, y, z,...) los de Σ*

(X, Y, Z,...) los de Γ*

La interpretación de f es:

     a) f(q, a, A) = {(q1, Z1), (q2, Z2),... (qn, Zn)

cuando el autómata se encuentra en el estado q, lee el símbolo de entrada a y tiene el símbolo A en la cima de la pila; el autómata pasará a algún estado qi (recordar que es no determinista), eliminará el símbolo A de la pila e introducirá en ella la palabra Zi , quedando la cabeza de Zi en la cima de la pila.

     b) f(q, λ, A) = {(q1, Z1), (q2, Z2),... (qn, Zn)

cuando el autómata se encuentra en el estado q, y tiene el símbolo A en la cima de la pila; el autómata pasará a algún estado qi (recordar que es no determinista), eliminará el símbolo A de la pila e introducirá en ella la palabra Zi , quedando la cabeza de Zi en la cima de la pila.

Se entiende que el resultado de la función f para las configuraciones (estado, símbolo de entrada y símbolo de pila) no explícitamente especificadas es el conjunto vacío. Estas representan configuraciones “muertas” del autómata.

Representación gráfica

AP=({a,b,c},{S,A,B,b},{p,q,r},S,p,f,{r})

f(p,a,S)={(p,SAB), (q,b)} f(p,λ,S)={(p,SAB)}

f(q,b,b)={(q,λ)} f(q,b,B)={(q,λ)} 

f(q,c,A)={(q,A),(q,λ)} 

f(q,λ,B)={(r,λ)}

• Cada estado corresponde a un nodo en el grafo y está etiquetado con el nombre del estado (si es un estado final se marca además con *)
• Cada transición (q, Z)∈f(p, a, A) corresponde a un arco del nodo p al nodo q y tiene la etiqueta (a,A,Z).
• Las etiquetas de los arcos pueden tener la forma: (a,A,λ), (a,A,B), (a,A,BC...), (λ,A,λ), (λ,A,B), (λ,A,BC...) siendo (a∈Σ, A,B,C∈Γ).
• No hay transiciones de forma: (..., λ, ...), (ab..., ..., ...) o (..., AB..., ...)

Descripción instantánea

Una descripción instantánea o configuración es una terna (q, x, Z) donde q∈Q, x∈Σ*, Z∈Γ* que define: el estado del autómata, la entrada que resta por leer y el contenido de la pila en un momento dado.

Movimientos

Un movimiento es el paso de una descripción instantánea a otra y se produce como resultado de la aplicación de la función f. Se representa por el símbolo ├ , que se lee como “precede a”.

 Hay dos tipos de movimientos:

(q, az, AZ) ├ (p, z, YZ) si (p, Y)∈f(q, a, A)

(q, z, AZ) ├ (p, z, YZ) si (p, Y)∈f(q, λ, A)

(q,p∈Q, a∈Σ, A∈Γ, z∈Σ*, Z,Y∈Γ*)

Utilizaremos el símbolo ├* para expresar el cierre transitivo y reflexivo de ├ . Es decir se entiende por Ii ├* Ij el resultado de una serie movimientos tales que Ii ├* Ij ⇒ Ii ├ Ik ......├ Ij

Lenguaje aceptado por un autómata a pila

Se describe el proceso de aceptación o rechazo de una palabra de Σ* mediante una sucesión de movimientos.

Un AP= (Σ, Γ, Q, A0, q0, f, F) puede reconocer palabras del alfabeto de entrada de dos formas distintas:

 - por estado final:

LF(AP) = {x | (q0, x, A0) ├* (p, λ, X), con p∈F, X∈Γ*}

- por vaciado de pila :

LV(AP) = { x | (q0, x, A0) ├* (p, λ, λ) con p∈Q}

LF(AP) y LV(AP) representan a los lenguajes reconocidos por el autómata AP por estado final y por vaciado de pila respectivamente.

Cuando la aceptación se realiza por vaciado de pila, el conjunto de estados finales F es irrelevante.

Equivalencia de AP

Dos autómata a pila (por vaciado de pila o por estado final), AP1 y AP2, son equivalentes, si aceptan el mismo lenguaje, es decir, si L(AP1)=L(AP2).

Autómatas a pila deterministas

Decimos que un autómata a pila es determinista si se verifica lo siguiente:

     1.  ∀ q∈Q, ∀ A∈Γ:

          f(q, λ, A) ≠ ∅ ⇒ ∀ a∈Σ: f(q, a, A) = ∅

     2. ∀q∈Q, ∀A∈Γ, ∀a∈ Σ∪{λ}:

         f(q, a, A) contiene como máximo un elemento.

A lo sumo, desde una configuración cualquiera existe como mucho un posible movimiento.

A diferencia de los autómatas finitos, se entiende que un AP es no determinista, a menos que se diga lo contrario.