Práctica Automatas A Pila PDF

Preview

Summary

Download Práctica Automatas A Pila PDF

Description

UNED – BERGARA

Teoría de autómatas, lenguajes y computación

BLOQUE III: AUTÓMATAS A PILA, LENGUAJES Y GRAMÁTICAS INDEPENDIENTES DEL CONTEXTO CAPÍTULO 6: AUTÓMATAS A PILA (AaP) 

Son los que entienden los LICs.



En inglés se les conoce como Pushdown Automata (PDA).



Son una extensión de los AFN-ℇ usados con los LR.



AaP = AFN-ℇ + pila LIFO.



Aceptación: 

Por haber llegado a un estado de aceptación.



Por vaciado de la pila, independientemente del estado en que se encuentre el autómata.



Las GICs se pueden transformar en AaP, y viceversa.



Ciertos AaP son deterministas, aceptando todos los LRs y solo algunos LICs.

6.1. Definición de AaP 

Primero de manera informal y luego formal.

6.1.1. Introducción informal 

Tenemos un AFN-ℇ con un pila LIFO para almacenar una cadena de “símbolos de pila”.



La pila permite al autómata “recordar” una cantidad finita de información.



En el “Control de estados finitos” se decide el siguiente estado en función del estado actual, del símbolo de entrada y del símbolo de la parte superior de la pila.



También se puede utilizar como símbolo de entrada ℇ y hacer hacer una transición “espontánea”.



En una transición: 

El AaP consume de la entrada el símbolo usado en la transición, a menos que use ℇ.



Realiza la transición quedando en un estado que puede ser el mismo u otro distinto al de partida.



Reemplaza el símbolo de la parte superior de la pila por cualquier cadena (ℇ, el símbolo que estaba u otro(s) símbolo(s)).



Ejemplo 6.1: Partimos del lenguaje Este es el lenguaje “w-w-reflejo” = palíndromos de longitud par sobre el alfabeto {0, 1}. Es un LIC generado por la GIC de la figura de la derecha (quitando las reglas 2 y 3). Vemos cómo se diseñaría el AaP para dicho lenguaje. 1. Partimos de q0, estado que representa que todavía no hemos llegado al centro ( = final de w). Mientras estamos en q0 los símbolos leídos serán almacenados en la pila. 2. Suponemos que hemos llegado al final de w → estado q1. La pila tendrá w, con el principio de la palabra en el fondo. Como el autómata es no determinista podemos estar en q1 y mantenernos también en q0. Por

JCM

Página 1

Teoría de autómatas, lenguajes y computación

UNED – BERGARA

ello, podemos continuar leyendo entradas y almacenándolas en la pila. 3. Ya en q1, se compararán los símbolos de entrada con el símbolo superior de la pila. Si son iguales, consumimos el símbolo de entrada, un símbolo de la pila y seguimos. Si no son iguales, la rama muere. 4. Si vaciamos la pila, habremos encontrado la cadena w seguida de wR y por ello, aceptaremos la entrada leída hasta el momento.

6.1.2. Definición formal de AaP 

Tiene 7 componentes: 

Q = conjunto finito de estados.



∑ = conjunto finito de símbolos de entrada.



 = (Gamma mayúscula) alfabeto de pila finito.



 = función de transición con tres argumentos, el estado de partida q, el símbolo de entrada a (o ℇ) y el símbolo de pila X. (q, a X) = (p, ). Donde p es el nuevo estado y  es la cadena de símbolos de la pila que reemplaza a X en la parte superior de la pila.  podría tomar, por ejemplo, el valor ℇ, X o YZ.





q0 = es el estado inicial.



Z0 es el símbolo inicial existente en la pila.



F = conjunto de estados de aceptación.

No se pueden mezclar los posibles resultados de . Por ejemplo, si no podríamos ir a p con ℇ ni a r con YZ.



Ejemplo 6.2: Diseño de un AaP P para aceptar el lenguaje Lwwr del Ejemplo 6.1. El símbolo de pila Z0 es necesario para marcar el fondo de la pila. Cuando lleguemos a este símbolo podremos hacer la transición al estado de aceptación q2.

La  responde a las siguientes reglas: 1. 2. 3. 4. 5.

6.1.3. Notación gráfica para los AaP 

Vamos a llegar a un esquema de transiciones: a)

Los nodos serán los estados del AaP.

b)

La flecha Inicio indica el estado inicial El doble círculo indica aceptación

c)

Las transiciones se marcan con arcos rotulados. “a, X / ” sería la etiqueta para el símbolo de entrada a con el símbolo de pila X y dejando  en la pila.



Ejemplo 6.3: el AaP del ejemplo anterior es el de la figura.

Página 2

JCM

UNED – BERGARA

Teoría de autómatas, lenguajes y computación

6.1.4. Descripciones instantáneas de un autómata a pila 

Se llama “descripción instantánea = ID (= instantaneous description)” o “configuración del AaP” al triplete (q, w, ), donde: 

q = estado en que se encuentra el autómata



w = lo que queda por leer de la entrada.



 = contenido de la pila, con el símbolo superior a la izquierda.

Con esta información sabemos en qué situación se encuentra el AaP. 

El equivalente a la ^ de los AF, en los AaP es la llamada notación “torniquete”, que nos permite conectar pares de descripciones instantáneas que representan uno o más movimientos del AaP.



Sea el AaP P = (Q, ∑, , , q0, Z0, F). Supongamos que (q, a, X) contiene (p, ). Esto es, que desde q, con a como entrada y X en la pila, tenemos, entre otras, la posibilidad de ir a p dejando  en la pila. Entonces, para todas las cadenas w  ∑* y   *, se cumple que: (q, aw, X) Ⱶ (p, w, ) Es decir, que podemos ir de q a p consumiendo a de la entrada (a puede ser ℇ), y reemplazando X por  en la cima de la pila. Como se ve, ni w ni  influyen en la decisión del autómata. Podemos usar también la notación



cuando se quiera dejar claro de qué AaP estamos hablando.

Para representar cero o más movimientos del AaP usaremos

 

Ejemplo 6.4: Sea el AaP de la página anterior y la entrada 1111 En la figura se ven las distintas configuraciones por las que puede pasar el autómata. Las flechas representan la relación Ⱶ. Como se puede ver, las configuraciones correctas son las indicadas por las flechas verdes.



Hay 3 principios importantes acerca de las ID y de sus transiciones para poder razonar sobre los AaP. Partimos de una secuencia de IDs válida para un AaP... 1.

La computación que se forma añadiendo la misma cadena de entrada al final de la entrada (2º componente) en cada ID también es válida.

2.

La computación formada añadiendo los mismos símbolos de pila a la parte inferior de la pila de cada ID también es válida.

3.

Si parte del extremo final de la entrada no se consume, entonces podemos eliminar dicho final de la entrada de cada ID y la computación resultante también será válida.

Los datos que no llega a ver P no pueden afectar a su funcionamiento. Los puntos (1) y (2) se enuncian en los siguientes teoremas.

JCM

Página 3

Teoría de autómatas, lenguajes y computación 

UNED – BERGARA

Teorema 6.5:

Aquí si  = ℇ tenemos el principio (1) y si w = ℇ tenemos el principio (2). 

Teorema 6.6:

6.2. Lenguajes de un AaP 

Los dos enfoques comentados:  

“Aceptación por estado final” → consume la entrada totalmente y llega al estado de aceptación. “Aceptación por pila vacía” → da como resultado un lenguaje formado por las cadenas que hacen que la pila se vacíe.



Estos enfoques son equivalentes, ya que el lenguaje L tiene un AaP que lo acepta por estado final si y solo si L tiene un AaP que lo acepta por pila vacía.



No obstante, para un AaP P, los lenguajes que acepta P por estado final y por pila vacía suelen ser diferentes.



Se puede convertir un AaP que acepta L por estado final en otro AaP que lo acepta por cadena vacía. Y al revés.

6.2.1. Aceptación por estado final 

donde q  F. Es decir, partiendo de la ID inicial con w como cadena de entrada, P consume w y llega a un estado de aceptación, siendo irrelevante el contenido de la pila. 

Ejemplo 6.7: Estamos trabajando con el AaP de Lwwr, que es el lenguaje de las cadenas pertenecientes a {0,1}* que tienen la forma wwR. Se demuestra que que el AaP del Ejemplo 6.2. acepta la cadena x por estado final si y solo si x es de la forma wwR. Demo en pág 196.

6.2.2. Aceptación por pila vacía (No entra en el temario). 

A pesar de que no entra es positivo valorar la similitud con el caso anterior.

para cualquier estado q. N(P) es el conjunto de entradas w que P puede consumir vaciando al mismo tiempo la pila. Página 4

JCM

UNED – BERGARA

Teoría de autómatas, lenguajes y computación

6.3. Equivalencia entre AaPs y GICs 

Los Ls definidos por los AaP son LICs.



Hay que demostrar que son equivalentes los LIC (que son los definidos por las GICs), los Ls aceptados por estado final por algún AaP y los Ls aceptados por pila vacía por algún AaL.



Para esto, seguiremos el siguiente recorrido:

6.3.1. De las gramáticas a los AaP 

Partimos de la GIC G y construimos un AaP que simule las derivaciones LM de G.



En general, cualquier forma sentencial por la izquierda que no es una cadena terminal puede escribirse como xA, donde A es la variable más a la izquierda, x es un símbolo terminal a la izquierda y  es la cadena de símbolos terminales y variables que aparece a la derecha. A es la “cola” de la forma sentencial por la izquierda. Si solo hubiera símbolos terminales en la forma sentencial, la cola sería ℇ.



Para construir el AaP a partir de la G lo que debe hacer el AaP es simular la secuencia de las formas sentenciales por la izquierda que la utiliza la G para generar una cadena terminal w. La cola de cada xA aparece en la pila con la A en la cima de la misma. “x” será consumida en la entrada, esto es, si w = xy y se cosume x, quedará y.



La construcción se puede precisar así. Sea G = (V, T, Q, S) una GIC. El AaP que acepta L(G) por pila vacía es: P = ({q}, T, V  T, , q, S) donde  se defina así: 1.

Para cada variable A,

2.

Para cada símbolo terminal a, (q, a,a) = {(q, ℇ)}



Ejemplo 6.12:



Teorema 6.13: Si un AaP se construye a partir de una GIC G mediante la construcción anterior, entonces N(P) = Conjunto de cadenas aceptadas por pila vacía = L(G).

JCM

Página 5

Teoría de autómatas, lenguajes y computación

UNED – BERGARA

Demo en 204.

6.3.2. De los AaP a las gramáticas 

Para todo AaP P podemos encontrar una GIC G que acepta el mismo lenguaje que P por pila vacía.



Teorema 6.14: Sea P = (Q, ∑, , , q0, Z0, F) un AaP. Entonces existe un GIC G tal que L(G) = N(P) (Recordar que N(P) es el conjunto de cadenas que son aceptadas por pila vacía).



Ejemplo 6.15: Se trata de convertir el AaP PN = ({q}, {i, e}, {Z}, N, q, Z) de la figura, en una gramática. Este AaP acepta los errores if/else por pila vacía. Dada la sencillez del autómata, solo hay 2 variables en la gramática: a) S = símbolo inicial b) [qZq] = único triplete que se puede construir a partir de los estados y de los símbolos de la pila de PN. Las producciones de la gramática son las siguientes:

Para simplificar, se puede reemplazar el triplete [qZq] por el símbolo A, por ejemplo. Así, la gramática quedaría finalmente así: S →A A → iAA |e Y puesto que A y S generan exactamente las mismas cadenas, podemos identificarlas como una y escribir la gramática completa como G = ({S}, {i, e}, {S → iSS | e}, S)

6.4. AaP determinista 

Por definición los AaP pueden ser no deterministas.



Sin embargo los AaP deterministas son importantes, ya que los analizadores sintácticos se suelen comportar como AaP deterministas (APD).

6.4.1. Definición de autómata a pila determinista 

Un AaP será determinista si no es posible elegir entre dos o más movimientos.



El AaP P = (Q, ∑, , , q0, Z0, F) es determinista si y solo si se cumplen las siguientes condiciones: 1. (q, a, X) tiene como máximo un elemento para cualquier q de Q, a de ∑ o a = ℇ, y X de .

Página 6

JCM

UNED – BERGARA

Teoría de autómatas, lenguajes y computación

2. Si (q, a, X) no está vacío para algún a de ∑, entonces (q, ℇ, X) tiene que estar vacío. 

Ejemplo 6.16: El lenguaje Lwwr es un LIC que no es reconocido por ningún APD. Sin embargo, si se introduce un marcador central “c” en el centro, se puede conseguir que sea reconocido por un APD. El alfabeto del lenguaje es {0,1}, por lo que el APD almacerá 0s y 1s en la pila hasta que aparezca el marcador central c. Pasa entonces a otro estado y comienza a emparejar el contenido de la pila con el de la entrada. Si llega al final de la pila, se acepta la cadena. En caso contrario, muere. El resultado es el APD de la figura.

6.4.2. LRs y APDs 

Los APD aceptan una clase de lenguajes que se encuentra entre los LRs y los LICs.



Teorema 6.17: Si L es un LR, entonces L = L(P) para algún APD P. Es decir, los lenguajes de los APD incluyen todos los LRs. Demostración: un APD puede simular un AFD. Sea el AFD A = (Q, ∑, A, q0, F), podemos llegar al APD P = (Q, ∑, {Z0}, P, q0, Z0, F), donde P(q, a, Z0) = {(p, Z0)} para todos los estados p y q de Q, tales que A(q, a) = p. Se cumple que

si y solo si ^A(q0, w) = p. Esto es, P simula A utilizando su estado.



Si queremos que el APD acepte por pila vacía, la capacidad de reconocimiento del lenguaje será bastante limitada.



Decimos que un L tiene la propiedad del prefijo si no existen dos cadenas distintas x e y de L tales que x sea un prefijo de y.



Ejemplo 6.18: Lwcwr tiene la propiedad del prefijo. Es decir, no pueden existir dos cadenas wcwR y xcxR, siendo una de ellas prefijo de la otra, a menos que sean la misma cadena. Supongamos que wcwR es un prefijo de xcxR, siendo w  x. Entonces w tiene que ser más corta que x. Por tanto, la c de wcwR aparece en una posición en la que xcxR tiene un 0 o un 1 (estará dentro de la primera x). Esto contradice la suposición de que wcwR es un prefijo de xcxR. También hay lenguajes sencillos que no tienen esta propiedad, por ejemplo, {0}* , ya que existen pares de cadenas de este lenguaje en los que una de las cadenas es prefijo de la otra, por lo que este lenguaje no tiene la propiedad de prefijo.



{0}* es regular, por lo tanto, no es cierto que todo LR sea N(P) para algún P.



Teorema 6.19: Un L es N(P) para un cierto AaP P si y solo si L tiene la propiedad prefijo y L es L(P') para algún APD P'.

6.4.3. APD y LICs 

Hemos visto que un APD puede aceptar lenguajes no regulares como Lwcwr. Se puede demostrar que este último lenguaje no es regular por el lema del bombeo.



Hay LICs como Lwwr que no pueden ser L(P) para ningún APD P.



Los lenguajes aceptados por los APD por estado final incluyen los LRs, pero están incluidos en los LIC.

JCM

Página 7

Teoría de autómatas, lenguajes y computación

UNED – BERGARA

6.4.4. APD y Gramáticas ambiguas. 

Teorema 6.20: Si L = N(P) para algún APD P, entonces L tiene una GIC no ambigua.



Teorema 6.21: Si L = L(P) para un APD P, entonces L tiene una GIC no ambigua.

6.5. Resumen del capítulo

Página 8

JCM...