LENGUAJES FORMALES Y AUTOMATAS

UNIVERSIDAD NACIONAL AUTÓNOMA DE MÉXICO

FACULTAD DE INGENIERÍA

LENGUAJES FORMALES Y AUTÓMATAS

EVALUACIÓN FINAL

ING. IGOR VALIENTE

SERVIN PICHARDO LUZ TAVATA

*******************************

AUTÓMATAS DE PILA (AP)

DEFINICIÓN.

Un autómata de pila (SA, en inglés stack automata) es un PDA con las siguientes dos características:

1.- La entrada es de dos direcciones, se encuentra en el modo de sólo lectura con señaladores de extremo.

2.- La cabeza de pila, además de colocar y eliminar movimientos en el tope de la pila puede acceder a la pila en el modo de sólo lectura, trasladándose hacia arriba o debajo de la pila sin reescribir ningún símbolo.

Un autómata de pila es una séxtupla M=(Q, ∑, Γ, qi, F, ∆) donde:

Q es el conjunto finito de estados.

∑ es el alfabeto finito de entrada

Γ es el alfabeto finito de pila

qiεQ es el estado inicial

F c Q es el conjunto de los estados finales

∆c(Q X ∑* X Γ*) X (Q X Γ*) es la relación de transición de los estados

FUNCIONAMIENTO

Un movimiento de un SA es determinado por el estado, la entrada y los símbolos de pila barridos, sea que el tope de la pila continua siendo barrido por la cabeza de pila o no. En un solo movimiento el estado puede cambiar la pila de entrada moviendo su posición hacia izquierda o derecha.

Si la cabeza de la pila no se encuentra en el tope, un movimiento también puede incluir el desplazamiento de la cabeza una posición alta o baja.

Si dicha cabeza se encuentra en el tope las acciones permitidas son:

1.- Introduce un símbolo en la pila.

2.- Retirar el símbolo del tope

3.- Moverse una posición más abajo en la pila sin añadir o retirar símbolos.

Durante las acciones uno y dos la cabeza de la pila permanece en el tope; en la acción tres abandona el tope y entra al modo sólo lectura, el cual abandona sólo si regresa al tope de la pila.

Inicialmente, la cabeza de entrada se encuentra en el extremo izquierdo y el control finito en un estado inicial designado, la pila consiste en un solo símbolo inicial designado. La aceptación se produce al entrar en un estado final.

Si nunca se efectúa más de un movimiento por cualquier actuación, el dispositivo es determínistico, si existe un número finito de alternativas para el movimiento en cualquier situación, el autómata es no determínistico. Si el dispositivo nunca retira un símbolo, entonces es no borrador.

Si la cabeza de entrada nunca se mueve hacia la izquierda, el autómata de pila es de una sola dirección.

Cuando no haya ninguna aseveración que indique lo contrario, suponemos un SA de dos direcciones, determinístico con permiso para borrar.

TIPOS DE PROBLEMAS A LOS QUE SE APLICAN
Donde se necesite un dispositivo matemático que reescribe el contenido almacenado en una estructura, habitualmente una pila de acuerdo don sus reglas de reescritura –transiciones-. Para el diseño de analizadores.

DISEÑO
Un autómata de este tipo se representa de la siguiente forma

El autómata de pila cuenta con un flujo de entrada y un flujo de control que puede encontrarse en uno de entre un número finito de estados. Uno de estos estados se designa como el inicial y por lo menos un estado es de aceptación.
Los autómatas de pila cuentan con una pila en donde pueden almacenar información para recuperarla mas tarde.
Para representar las transiciones de un autómata de pila se utiliza un diagrama de transiciones que es semejante al de un autómata finito, los estados se representan con círculos y las transiciones por medio de arcos entre los círculos. La rotulación de los arcos lleva más información. Un arco de p a q que representa la transición (p,x,y;q,z) tendría una etiqueta x,y;z.
EJEMPLOS DE AP
Ejemplo: considerar la siguiente gramática independiente del contexto.

S zMNz
M aMa
M z
N bNb
N z
El siguiente diagrama de transiciones de un autómata de pila construido a partir de la gramática anterior

Análisis completo de la cadena zazababa que efectúa el autómata de pila.

Ejemplo
Sea L = {anbn n ≥ 0}
Un APN que reconoce ese lenguaje es: Q = {q0,q1} F = {q0,q1} Σ = {a, b} Γ = {a} Δ = {((q0,a,ε), (q0,a)), ((q0,b,a), (q1,ε)),((q1,b,a), (q1,ε))}

Ejemplo
Sea L={wwR w  {a,b}*} Q = {q0,q1} F = {q0,q1} Σ = {a,b} Γ = {a,b} Δ = {((q0,a,ε), (q1,a)), ((q0,b,ε), (q1,b)), ((q0,ε,ε), (q1,ε)), ((q1,a,a), (q1,ε)), ((q1,b,b), (q1,ε)) }

MÁQUINA DE TURING

DEFINICIÓN
Una máquina de Turing se representa por:
M = (Q, Σ, Γ, δ, q0, B, F)

En donde:

Q es el conjunto finito de estados

Γ es el conjunto finito de símbolos de cinta admisibles

B es símbolo de Γ, espacio en blanco

Σ es el subconjunto de Γ que no incluye a B, es el conjunto de los símbolos de entrada

Δ es la función de movimientos siguiente, una trasformación de Q X Γ a Q X Γ X (L,R) ( δ puede permanecer indefinida para algunos argumentos)

q0 en Q es el estado inicial

F C Q es el conjunto de estados finales.

La máquina de Turing es una autómata que se mueve sobre una secuencia lineal de datos.

Para cada instante lee un solo dato de la secuencia (un carácter) y realiza ciertas acciones en base a la tabla que tiene su estado actual y el último dato leído. Escribiendo nuevos datos en la secuencia, recorriendo la secuencia en ambos sentidos y cambiando de estado dentro de un conjunto finito de estados posibles.

La máquina de Turing es una abstracción matemática más que un dispositivo físico o mecánico. La denominación de máquina es por su funcionamiento descrito en términos de operaciones individuales sencillas que sugieren de igual forma una implementación real sencilla o simple.

FUNCIONAMIENTO

El modelo básico tiene un control finito, una cinta de entrada que está dividida en celdas y una cabeza de cinta que barre una celda de la cinta a la vez.
La cinta tiene una celda que está más a la izquierda, pero se extiende de manera finita hacia la derecha. Cada celda de la cinta puede contener exactamente un símbolo de un número finito de símbolos de cinta. Inicialmente, las n celdas están más a la izquierda, para alguna n >=0 finita, sujetando la entrada, que es una cadena de símbolos escogidos de un subconjunto de los símbolos de dicha cinta llamados símbolos de entrada.
Cada una del número finito de las celdas restantes sujetan el espacio en blanco, que es un tipo especial de símbolo que no es de entrada.
En un movimiento, dependiendo del símbolo barrido por la cabeza de la cinta y del estado del control finito, realiza las siguientes acciones:
1.- Cambiar de estado
2.- Imprimir un símbolo en la celda de la cinta que está siendo barrida, sustituyendo lo que se encontraba ahí escrito
3.- Mover la cabeza a una celda hacia la izquierda o la derecha.
La diferencia entre la máquina de Turing y un autómata finito de dos direcciones estriba en la capacidad de la primera para cambiar los símbolos de la cinta.

TIPOS DE PROBLEMAS A LOS QUE SE APLICA

Modela la capacidad de cálculo de una computadora de propósitos generales, el llamado a conjuntos de manera recursiva enumerables, y a su llamado de funciones parcialmente recursivas.
Su extraordinaria importancia es la capacidad de resolver cualquier problema matemático en el momento de ser reducido a un algoritmo.

DISEÑO

Representación del comportamiento de la máquina de Turing capaz de sumar 1 a cualquier

número unario. El alfabeto solo tiene dos símbolos: Vacío (0) y valor (1). La máquina puede adoptar tres estados diferentes numerados del 0 al 2 (es costumbre señalar el estado inicial con 0). El movimiento H ("Halt") significa no desplazar el cabezal. En este caso la máquina se detiene (o entra en un bucle sin fin).

También es posible representar la tabla de acción mediante un grafo.
Los diferentes estados internos se representan por círculos. Los cambios de estado con flechas a las que se añade una leyenda. Generalmente se utiliza una flecha para señalar el estado inicial.

EJEMPLOS

Supongamos una máquina de Turing con un alfabeto unario, en la que el nulo (ausencia de dato) lo señalamos con 0. La máquina puede tener cinco estados que denominamos {e0, e1, e2, e3, e4}. El estado inicial es e0

1.- Se lee un carácter c (en nuestro caso es necesariamente 0 o 1)
2.- Se mira en la tabla que fila corresponde a la combinación ex/c.
3a.- Si no existe entrada la máquina se detiene.
3b.- Si existe entrada se ejecuta la instrucción (columnas en marrón claro) en el siguiente orden: 3b1.- Se escribe en la posición actual el carácter señalado (puede ser el mismo que había).
3b2.- Se mueve el cabezal una posición a izquierda o derecha.
3b3.- Se pasa al estado señalado en la última columna (puede implicar no cambiar de estado).
3b4.- Se repite el ciclo desde el punto 1.

P1: La máquina ejecuta el primer paso. Arranca en el estado e0, donde lee un 1; entonces, de acuerdo con su tabla de acción escribe un 0 en esa posición, se mueve a la derecha y entra en estado e1.
P2: En e1 lee un 1, escribe un 1 y se mueve a la derecha. Sigue en e1.
P3: En e1 lee 0, escribe 0, se mueve a la derecha y cambia a e2
P4: En e2 lee 0, escribe 1, se mueve a la izquierda y cambia a e3
P5: En e3 lee 0, escribe 0, se mueve a la izquierda y cambia a e4
P6: En e4 lee 1, escribe 1, se mueve a la izquierda y sigue en e4
El proceso sigue la misma lógica a través de los sucesivos pasos hasta llegar al último.
P15: En e0 lee 0; no existe ninguna entrada en la tabla para esta combinación, por lo que el autómata se detiene. Comprobamos como al final ha escrito en la cinta la cantidad esperada: 11011.

EJEMPLO