Lenguajes Libres de Contexto: marzo 2011

miércoles, 30 de marzo de 2011

Automatas PushDown (Presentan: Ing. Anastasio, Ing. Garcia e Ing. Bautista

AUTÓMATA PUSHDOWN

Este modelo posee dos cintas con celdas iniciales a la izquierda e infinitas celdas a la derecha. Una de sus cintas es para almacenar los símbolos de entrada o palabra a ser analizada y solo se realizan lecturas sobre ella. La otra cinta funciona como una pila ( primer símbolo en entrar, último en salir) sobre ella se introducen y extraen símbolos especiales, a partir de un cabezal de lectura / escritura. Los cabezales están vinculados a una unidad de control.

Inicialmente la cinta de entrada contiene blancos, al igual que la cinta de tipo pila. Se coloca los símbolos que representan la palabra a ser analizada a partir del extremo izquierdo de la cinta de entrada. El cabezal de la cinta de entrada se encuentra, como Estado Inicial sobre el primer símbolo del extremo izquierdo. El cabezal de la cinta de tipo pila se posiciona sobre el tope de la pila o extremo izquierdo de la misma.

Recordemos que el cabezal de lectura de la cinta de entrada solo puede leer un símbolo y desplazarse hacia la derecha. Por otro lado el cabezal de la cinta tipo pila puede escribir un símbolo (generalmente auxiliar) y desplazarse a la derecha o descargar (borrar) un símbolo y desplazarse a la derecha.

Formalmente, un autómata con pila puede ser descrito como una séptupla

M = (S,Σ,Γ,δ, s, Z, F)

donde:

Σ y $Γ$ son alfabetos de entrada, de la cadena y de la pila respectivamente;
S un conjunto de estados;
$\delta: S \times (\Sigma \cup \{\epsilon \} ) \times \Gamma \rightarrow \mathcal{P} ( S \times \Gamma^*)$
$s \in S$ es el estado inicial;
$Z\ \in \Gamma$ es el símbolo inicial de la pila;
$F \subseteq S$ es un conjunto de estados de aceptación o finales.

La interpretación de $\delta (s, a, Z) = \{ (s_1, \gamma_1), (s_2, \gamma_2), \ldots, (s_n, \gamma_n) \},$ con $s, p_i \in Q, a \in (\Sigma \cup \{ \epsilon \} ), \gamma_i \in \Gamma$ es la siguiente:

Cuando el estado del autómata es

s

, el símbolo que la cabeza lectora está inspeccionando en ese momento es

a

, y en la cima de la pila nos encontramos el símbolo

Z

, se realizan las siguientes acciones:

Si $a \in \Sigma$ , es decir no es la palabra vacía, se avanza una posición la cabeza lectora para inspeccionar el siguiente símbolo.
Se elimina el símbolo Z de la pila del autómata.
Se selecciona un par $(p i,γ i)$ de entre los existentes en la definición de $δ(s, A, Z)$ , la función de transición del autómata.
Se apila la cadena $\gamma_i = A_1 A_2 \ldots A_k$ en la pila del autómata, quedando el símbolo $A 1$ en la cima de la pila.
Se cambia el control del autómata al estado $p i$ .

Un autómata de 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 de 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.

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.

Ejemplo de un Autómata de Pila:

Sea el Siguiente Lenguaje L= { aⁿ(bc^m)^n-1|m³1,n³1 }

TABLA DE TRANSICIONES DEL AUTÓMATA ANTERIOR

Num. Tran.	Estado	Entrada	Símbolo de stack	acciones
1	p	a	S	(p,SAB)
2	p	a	S	(q,b)
3	p	l	S	(p,SAB)
4	q	b	b	(q,l)
5	q	b	B	(q,l)
6	q	c	A	(q,A)
7	q	c	A	(q,l)
8	q	l	B	(r,l)




	Otras combina-ciones				ninguna

A continuación se colocan 3 archivos recopilados de Internet de respetables ingenieros e informáticos:

Link Directo: http://www.dirinfo.unsl.edu.ar/~ayl/Teorias/Apunte_Teoria/Teoria4-07_2.pdf

Link directo: http://www.exa.unicen.edu.ar/catedras/ccomp1/Apunte4.pdf

FUENTES BIBLIOGRÁFICAS:
paginas web...

http://www.ia.urjc.es/grupo/docencia/automatas_itis/apuntes/capitulo11.pdf
http://es.wikipedia.org/wiki/Aut%C3%B3mata_con_pila

LIBROS COMO...
1.-TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES. AUTÓMATAS Y COMPLEJIDAD
KELLY DEAN

EDITORIAL PRENTICE HALL

PRESENTARON:

Leen Christian Anastasio Hernández .

Marissey Bautista Alonso.

Jorge Eduardo García Morales.

4.1 DEFINICION FORMAL DE UNA MAQUINA TURING

La Máquina de Turing (MT) fue introducida por Alan M. Turing en 1936, y puede considerarse como un modelo abstracto que formaliza la idea Intuitiva de algoritmo.

(MT) Es un modelo computacional que realiza una lectura/escritura de manera automática sobre una entrada llamada cinta, generando una salida en esta misma. Este modelo está conformado por un alfabeto de entrada y uno de salida, un símbolo especial llamado blanco (normalmente b, Δ o 0), un conjunto de estados finitos y un conjunto de transiciones entre dichos estados.

Su funcionamiento se basa en una función de transición, que recibe un estado inicial y una cadena de caracteres (la cinta, la cual es finita por la izquierda) pertenecientes al alfabeto de entrada. Luego va leyendo una celda de la cinta , borrando el símbolo , escribir el nuevo símbolo perteneciente al alfabeto de salida y finalmente avanza a la izquierda o a la derecha (solo una celda a la vez), repitiendo esto según se indique en la función de transición, para finalmente detenerse en un estado final o de aceptación, representando así la salida.

Una máquina de Turing con una sola cinta puede ser definida como una 7-tupla ;

donde:

es un conjunto finito de estados.

es un conjunto finito de símbolos distinto del espacio en blanco,denominado alfabeto de máquina o de entrada.

es un conjunto finito de símbolos de cinta, denominado alfabeto de cinta.

es el estado inicial.

es un símbolo denominado blanco, y es el único símbolo que se puede repetir un número infinito de veces.

es el conjunto de estados finales de aceptación.

Es una función parcial denominada función de transición,donde es un movimiento a la izquierda y es el movimiento a la derecha.

La máquina de Turing puede considerarse como un autómata capaz de reconocer lenguajes formales. En ese sentido es capaz de reconocer los lenguajes recursivamente enumerables, de acuerdo a la jerarquía de Chomsky.

Su potencia es, por tanto, superior a otros tipos de autómatas, como el autómata finito, o el autómata con pila, o igual a otros modelos con la misma potencia computacional. Las maquinas de Turing se pueden representar mediante grafos particulares, también llamados diagramas de estados finitos, de la siguiente manera:

Esta Máquina de Turing está definido sobre el alfabeto Σ={a,b,c}, posee el conjunto de estados

Q={qo,q1,q2,q3,q4,q5,q6}, con las transiciones que se pueden ver. Su estado inicial es q1 y el estado final es q0, el lenguaje de salida δ={X,Y,Z,B} siendo B el símbolo denominado Blanco.

Esta Máquina reconoce la expresión regular de la forma {a^n b^n c^n,n>=0} .

*Los estados se representan como vértices, etiquetados con su nombre en el interior.

*Una transición desde un estado a otro, se representa mediante una arista dirigida que une a estos vértices, y esta rotulada por símbolo que lee el cabezal/símbolo que escribirá el cabezal, movimiento del cabezal .

*El estado inicial se caracteriza por tener una arista que llega a él, proveniente de ningún otro vértice.

*El o los estados finales se representan mediante vértices que están encerrados a su vez por otra circunferencia.

¿COMO FUNCIONA UNA MAQUINA DE TURING?

Una máquina de Turing es un dispositivo que transforma un INPUT en un OUTPUT después de algunos pasos. Tanto el INPUT como el OUPUT constan de números en código binario (ceros y unos). En su versión original la máquina de Turing consiste en una cinta infinitamente larga con unos y ceros que pasa a través de una caja.

La caja es tan fina que solo el trozo de cinta que ocupa un bit (0 ó 1) está en su interior. La máquina tiene una serie de estados internos finitos que también se pueden numerar en binario. Para llevar a cabo algún algoritmo , la máquina se inicializa en algún estado interno arbitrario. A continuación , se pone en marcha y la máquina lee el bit que se encuentra en ese momento en su interior y ejecuta alguna operación con ese bit (lo cambia o no, dependiendo de su estado interno). Después se mueve hacia la derecha o hacia la izquierda, y vuelve a procesar el siguiente bit de la misma manera. Al final se para, dejando el resultado al lado izquierdo por ejemplo.

11011i→Una instrucción típica podría ser: 01

VARIANTES DE LA MAQUINA DE TURING

La traducción es como sigue: si la máquina se encuentra en el estado interno 0 y lee 1 en la cinta, entonces pasará al estado interno 1101 (13), escribirá 1 y se moverá hacia la izquierda un paso (la cinta se moverá hacia la derecha). A continuación es conveniente inventar una notación para la secuencia del INPUT. Esta notación se llama notación binaria expandida. Consiste en cambiar la secuencia original binaria por otra construida de la siguiente forma: el 0 se cambia por 0 y el 1 por 10 y se ponen un cero a la izquierda y/o a la derecha del resultado si empieza o acaba en 1 respectivamente. Así por ejemplo, el número 13 que en binario es 1101 es en binario expandido 1010010 con un cero delante por esta última regla 01010010. Para volver al original hay que contraer el binario expandido con la siguiente regla: Empezamos a leer por la izquierda el binario expandido. Cuando encontremos un 0 tomamos nota de cuántos 1 hay hasta llegar al siguiente 0 y lo escribimos. Si encontramos que hay dos 0 seguidos , apuntaríamos un 0 porque no habría ningún 1.Veamos con el 13 cómo se haría.

El primer 0 se encuentra en la primera posición y el siguiente 0 está en la posición 3. Entre los dos solo hay un 1. Lo anotamos. Seguidamente hay un 1, y después un 0, entonces apuntamos 1 porque hay un 1 entre medias de ellos. Esto es lo que se hace sucesivamente y encontramos: 1101 que es el número original.

¿QUE SON Y COMO FUNCIONAN?

Una máquina de Turing consiste, básicamente, en una cinta infinita, dividida en casillas. Sobre esta cinta hay un dispositivo capaz de desplazarse a lo largo de ella a razón de una casilla cada vez. Este dispositivo cuenta con un cabezal capaz de leer un símbolo escrito en la cinta, o de borrar el existente e imprimir uno nuevo en su lugar. Por último, contiene además un registro capaz de almacenar un estado cualquiera, el cual viene definido por un símbolo.

Los símbolos que definen el estado del dispositivo no tienen por que coincidir con los símbolos que se pueden leer o escribir en la cinta. En los programas presentados en el artículo, los posibles símbolos a leer o escribir en la cinta son el 0 y el 1, y los posibles estados se representan con letras mayúsculas. En el emulador , existe un cambio en la representación del estado , usando para ello los números del 0 al 99, para permitir un mayor número de ellos. La máquina tiene un funcionamiento totalmente mecánico y secuencial. Lo que hace es leer el símbolo que hay en la casilla que tiene debajo. Después toma el símbolo del estado en que se encuentra. Con estos dos datos accede a una tabla, en la cual lee el símbolo que debe escribir en la cinta, el nuevo estado al que debe pasar y si debe desplazarse a la casilla izquierda o derecha.

Ejemplo Definimos una máquina de Turing sobre el alfabeto {0,1}, donde 0 representa el símbolo blanco. La máquina comenzará su proceso situada sobre un símbolo “1″ de una serie.

La máquina de Turing copiará el número de símbolos “1″ que encuentre hasta el primer blanco detrás de dicho símbolo blanco. Es decir , situada sobre el 1 situado en el extremo izquierdo, doblará el número de símbolos 1, con un 0 en medio. Así, si tenemos la entrada “111″ devolverá “1110111″, con “1111″ devolverá “111101111″, y sucesivamente.

El conjunto de estados es {s1,s2,s3,s4,s5} y el estado inicial es s1.
La tabla que describe la función de transición es la siguiente:

El funcionamiento de una computación de esta máquina se puede mostrar con el siguiente ejemplo (en negrita se resalta la posición de la cabeza lectora/escritora):

Vemos que esta máquina no hace gran cosa. Sin embargo, una máquina de Turing puede hacer cosas útiles, tales como suma r dos números, multiplicarlos, copiarlos, etc. Disponiendo de una máquina con el suficiente número de estados, podríamos hacer con ella cualquier operación que un ordenador normal pudiese realizar.

Las máquinas de Turing plantean una deducción bastante curiosa: dado que en ellas se puede realizar cualquier trabajo computable , es posible programarlas para que simulen el comportamiento de un potente ordenador. Y como una máquina de Turing puede ser codificada en cualquier ordenador, por pequeño que sea, sería posible (si disponemos de memoria suficiente, claro) emular en nuestro ordenador de casa una máquina de Turing que simule un superordenador. Esto significa que todos los ordenadores pueden realizar exactamente el mismo tipo de tareas , y que los cálculos que pueda realizar el más grande los puede llevar a cabo también el más pequeño. La única diferencia sería, obviamente, la velocidad.

bibliografia:

*Fernando Cuartero

Jose A. Gamez Jose M.

Puerta Departamento de Informatica

* Matemáticas Discretas

Richard Jonhsonbaugh

martes, 29 de marzo de 2011

3.7.- Eliminación de la ambigüedad.

Una GLC es ambigua si existe una cadena w Î L(G) que tiene más de una derivación por la izquierda o más de una derivación por la derecha o si tiene dos o más árboles de derivación. En caso de que toda cadena w Î L(G) tenga un único árbol de derivación, la gramática no es ambigua.

Ejemplo: La gramática S ® aS| Sa | a es ambigua porque aa tiene dos derivaciones por la izquierda

S Þ aS Þ aa S Þ Sa Þ aa

Esta gramática genera el lenguaje a+ que también es el lenguaje generado por la gramática no ambigua S ® aS | a.

EJEMPLO

•La gramática para expresiones aritméticas sobre las variables x y y:

–E ® E + E

–E ® E * E

–E ® x

–E ® y

es ambigua porque la cadena x + y * x tiene dos árboles de derivación:

TIPOS DE AMBIGÜEDAD

Dentro del estudio de gramáticas existen dos tipos fundamentales de ambigüedad, los cuales son:

Ambigüedad Inherente:
Las gramáticas que presentan este tipo de ambigüedad no pueden utilizarse para lenguajes de programación, ya que por más transformaciones que se realicen sobre ellas, nunca se podrá eliminar completamente la ambigüedad que presentan.

Un lenguaje L es inherentemente ambiguo si todas sus gramáticas son ambiguas; si existe cuando menos una gramática no ambigua para L, L no es

ambiguo.

– El lenguaje de las expresiones no es Ambiguo

– Las expresiones regulares no son ambiguas

Ejemplo de un lenguaje inherentemente ambiguo:

L = {aⁿbⁿc^md^m | n ³ 1, m ³ 1} È {aⁿb^mc^mdⁿ| n ³ 1, m ³ 1}

L es un LLC:

S ® AB | C

A ® aAb | ab C ® aCd | aDd

B ® cBd | cd D ® bDc | bc

La gramática es ambigua: hay cadenas con más de una

derivación más izquierda:

Considere: aabbccdd (m = n = 2)

S ⇒ AB ⇒ aAbB ⇒ aabbB ⇒ aabbcBd ⇒ aabbccdd

S ⇒ C ⇒ aCd ⇒ aaDdd ⇒ aabDcdd ⇒ aabbccdd

- El lenguaje:

- L = {aⁿbⁿc^md^m | n ³ 1, m ³ 1} È {aⁿb^mc^mdⁿ | n ³ 1, m ³ 1}

- La gramática

- S ® AB | C

A ® aAb | ab C ® aCd | aDd

B ® cCd | cd D ® bDc | bc

_ ¿Por qué todas las gramáticas para este lenguaje son

ambiguas?

– Considere cualquier cadena con m = n

– ¡Siempre habrá dos derivaciones para estas cadenas!

Ambigüedad Transitoria:
Este tipo de ambigüedad puede llegar a ser eliminada realizando una serie de transformaciones sobre la gramática original. Una vez que se logra lo anterior, la gramática queda lista para ser reconocida por la mayor parte de los analizadores sintácticos. (Se le considera "ambigüedad" porque existen métodos para realizar análisis sintáctico que no aceptan gramáticas con estas características)

Dónde se presenta la Ambigüedad Transitoria generalmente la ambigüedad se presenta cuando existen producciones con factores comunes (distintas alternativas para un símbolo no-terminal que inician de la misma forma); ó cuando existen producciones que son recursivas izquierdas (producciones para un símbolo no-terminal en las cuales el primer símbolo de su forma sentencial es ese mismo símbolo no-terminal).

¿Cómo solucionar el problema de la Ambigüedad Transitoria?

Para eliminar este tipo de ambigüedad, es necesario, primero eliminar:
- Factores comunes izquierdos inmediatos y No-inmediatos.
- Recursividad izquierda inmediata y No-inmediata.

ELIMINACIÓN DE LA AMBIGÜEDAD.

– No existe un algoritmo que nos indique si una GIC es ambigua

– Existen LIC que sólo tienen GIC ambiguas: inherentemente ambiguos

– Para las construcciones de los lenguajes de programación comunes existen técnicas para la eliminación de la ambigüedad

– Ejemplo: causas de ambigüedad en la siguiente gramática

• No se respeta la precedencia de operadores

• una secuencia de operadores idénticos puede agruparse desde la izquierda y desde la derecha. Lo convencional es agrupar desde la izquierda.