Automatas De Pila

AUTOMATAS DE PILA Y LENGUAJES INDEPENDIENTES DEL CONTEXTO

Autómatas de Pila y Lenguajes Independientes de Contexto

Índice Cuestionario Autómatas

4 5

Características

8

Principio de Pre Análisis

9

Formalización de los AP Límites de los Autómatas de Pila Proceso de reconocimiento de una cadena

10 12 13

Lenguajes libres de contexto

15

Gramáticas independientes del contexto Gramáticas libres del contexto BNF

17 18 21

Bibliografía de Avram Noam Chomsky Respuestas Bibliografía

22 23 25

07/03/2009

2

Autómatas de Pila y Lenguajes Independientes de Contexto

07/03/2009

Objetivo

Al termino de esta presentación se contará con la capacidad de identificar los autómatas de pila y sus diferentes tipos, así como los lenguajes independientes de contexto.

3

Autómatas de Pila y Lenguajes Independientes de Contexto

07/03/2009

Cuestionario 1. ¿Qué es un autómata de Pila? 2. ¿Para que sirve la pila de los Autómatas? 3. ¿Qué es el principio de pre análisis? 4. ¿Mencione el proceso de reconocimiento de una cadena? 5. ¿Qué significa un GIC? 6. ¿Para que nos sirve un GIC? 7. ¿Cuantos tipos de gramática existen según la clasificación de Chomsky y cuales son? 8. ¿A que se debe el nombre “Libre de Contexto”?

4

Autómatas de Pila y Lenguajes Independientes de Contexto

07/03/2009

Autómata Al igual que con los lenguajes regulares podemos definir un autómata como una máquina reconocedora de cadenas (palabras) de un determinado lenguaje.

Los autómatas son dispositivos de computo que operan como una maquina de estados finitos, las cuales realizan un encadenamiento automático y continuo de operaciones capaces de procesar una información de entrada para producir otra de salida. Por lo general los autómatas finitos no son lo suficientemente poderosos para aceptar el control de enlace lógico LLC (Logical Link Control) quien es el que define la forma en que los datos son transferidos sobre el medio físico, proporcionando servicio a las capas superiores La idea es agregar “algo” a los Autómatas Finitos para que de alguna manera se incremente

5

Autómatas de Pila y Lenguajes Independientes de Contexto

07/03/2009

Por tal motivo surgen los Autómatas de Pila, que al igual que un Autómata Finito, 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 de aceptación La principal diferencia es que los Autómatas de pila cuentan justamente con una pila en donde se puede almacenar información para recuperarla más tarde

6

Autómatas de Pila y Lenguajes Independientes de Contexto

07/03/2009

Los símbolos que pueden almacenarse en esta pila se conocen como símbolos de pila de la maquina, constituyen un conjunto finito que puede incluir algunos símbolos definiendo el alfabeto de la maquina y quizá algunos símbolos adicionales que se utilizan como marcas internas. Si una maquina inserta un símbolo especial en la pila antes de efectuar algún otro cálculo, entonces ese símbolo en la cima de la pila puede usarse como indicador de pila vacía para cálculos posteriores, dicho símbolo es #

7

Autómatas de Pila y Lenguajes Independientes de Contexto

07/03/2009

Características La Pila funciona de manera que el último carácter que se almacena en ella es el primero en salir (orden LIFO), como si apiláramos platos uno encima de otro, y naturalmente el primero que quitaremos es el último que hemos colocado.

Un aspecto crucial de la pila es que sólo podemos modificar el “tope” de la pila, que es el extremo por donde entran o salen los caracteres. Los caracteres a la mitad de la pila no son accesibles sin quitar antes los que están encima de ellos La pila tendrá un alfabeto propio que puede o no coincidir con el alfabeto de la palabra de entrada. Esto se justifica porque puede ser necesario introducir en la pila caracteres especiales usados como separadores según las necesidades de diseño del autómata

8

Autómatas de Pila y Lenguajes Independientes de Contexto

07/03/2009

Principio de Pre Análisis

Técnica que permite a los autómatas de pila observar uno o varios símbolos más allá de donde se encuentra la cabeza lectora del autómata, pero sin leerlos realmente.

Esta técnica permite superar el no determinismo de algunos autómatas de pila.

9

Autómatas de Pila y Lenguajes Independientes de Contexto

Formalización de los AP Un Autómata de Pila es un séxtuplo (K, ∑, Г, ∆, s, F), donde : K es un conjunto de estados

∑ es el alfabeto de entrada Г es el alfabeto de la pila

S ∈ K es el estado inicial F

K es un conjunto de estados finales

∆ esta representa la siguiente tabla

(s, a, E)

(s, a)

(s, b, E)

(s, b,)

(s, c, E)

(f, E )

(f, a, a)

(f, E )

(f, b, b)

(f, E )

07/03/2009

10

Autómatas de Pila y Lenguajes Independientes de Contexto

∆

07/03/2009

(K x ∑* x Г*) x (K x Г*) es la relación de transición.

Ahora describiremos el funcionamiento de los AP. Si tenemos una transición ((p, u, β)(q, )) ∈ ∆, el AP hace lo siguiente: Estando en el estado p, consiste u de la entrada;

Saca β de la pila; Llega a un estado q;

Mete

en la pila

Las operaciones típicas de las pilas -el “push” y el “pop”- pueden ser vistas como casos particulares de las transiciones de nuestro AP; en efecto, si sólo queremos meter la cadena a la pila, se haría con la transición ((p, u, E)(q, )) (“push”), mientras que si sólo queremos sacar caracteres de la pila de hará con la transición ((p, u, β)(q, E)) (“pop”).

11

Autómatas de Pila y Lenguajes Independientes de Contexto

07/03/2009

Límites de los Autómatas de Pila Lema de bombeo para lenguajes independientes del contexto •

Si L es un lenguaje independiente del contexto con un número infinito de cadenas, existirá en L una cadena con la forma svuwt, siendo v o w no vacías, y también existirán en L cadenas de la forma sv”uw”t para todo n>0.

Autómatas de pila deterministas •

En cada momento tienen una y sólo una opción posible

12

Autómatas de Pila y Lenguajes Independientes de Contexto

07/03/2009

13

Proceso de reconocimiento de una cadena:  Se parte del estado inicial y la pila vacía  Se lee la cadena símbolo a símbolo de izquierda a derecha  Por cada símbolo leído se produce una transición desde el estado actual a otro a través de la flecha cuyo símbolo de entrada coincida con el símbolo leído, siempre y cuando la cabecera de la pila coincida con el símbolo de pila que figura a la izquierda del punto y coma  La cabecera de la pila es sustituida en cada transición por el símbolo de la pila a la derecha del punto y coma en la etiqueta de la flecha  El autómata puede realizar transiciones entre estados sin consumir símbolos de entrada o símbolo de pila a través de flechas en las que en el lugar correspondiente de la etiqueta aparezca el símbolo λ  La cadena es reconocida si es posible que el autómata alcance un estado de aceptación, estando completamente con sumida la cadena de entrada

Autómatas de Pila y Lenguajes Independientes de Contexto

07/03/2009

14

Coffee Coffee Break

ak

Coffee

Autómatas de Pila y Lenguajes Independientes de Contexto

07/03/2009

15

Lenguajes Libres de Contexto

Los LLC se describen mediante las Gramáticas Libres de Contexto (GLC). Todos los LR son LLC, pero no todos los LLC son LR. Los LLC (que no sean LR) no pueden denotarse mediante expresiones regulares ni pueden ser reconocidos mediante AF. Los LLC se utilizan para especificar la mayoría de los lenguajes de programación

Autómatas de Pila y Lenguajes Independientes de Contexto

07/03/2009

Ejemplos 1. G = (VN, VT, E, P) con VT= {id, num,+,*,(,)} VN = {E}

P:

1. E→E+E 2. E→E*

3. E→(E)Derivar la palabra id * (id+num) * id 4. E→id

5. E→num Hallar gramática que genera el lenguaje regular denotado por la expresión regular a*b*

Hallar gramática que genera el lenguaje anbn , n >= 0 Hallar gramática que describe el lenguaje de los palíndromosformados por a’s y b’s

16

Autómatas de Pila y Lenguajes Independientes de Contexto

07/03/2009

17

Gramáticas Independientes del Contexto Son el método más popular utilizado para describir la sintaxis de los lenguajes de programación.

Existen distintos tipos de gramáticas y asociado a cada uno de ellos hay un autómata. Chomsky definió cuatro tipos: 1- Gramáticas regulares. 2- Gramáticas libres del contexto. 3- Gramáticas dependientes del contexto. 4- Gramáticas irrestrictas. Las más usadas en el área de compiladores son las gramáticas libres del contexto y las gramáticas regulares.

Autómatas de Pila y Lenguajes Independientes de Contexto

07/03/2009

Gramáticas Libres del Contexto Su principal característica es la de generar cadenas en modalidad espejo. Su importancia radica en que permiten describir los aspectos sintácticos de los lenguajes de programación. Es decir, como debe escribirse correctamente un programa.

Sin embargo tienen sus limitaciones desde el punto de vista semántica (declaración y uso de identificadores en Pascal). El nombre “libre de contexto” se debe a que cada una de las producciones pueden ser aplicadas independientemente del contexto en donde aparezca un no terminal en una forma sentencial. Sus producciones responden al modelo: A →α, donde A ∈VN y α∈(VN ∪VT)*

18

Autómatas de Pila y Lenguajes Independientes de Contexto

07/03/2009

En sus reglas aparece a la izquierda un único símbolo no terminal , y a la derecha cualquier combinación de símbolos terminales y no terminales, o la palabra vacía Derivaciones:

árboles que se pueden leer de diferentes formas Derivación por la derecha: siempre se aplican las reglas de reescritura al símbolo no terminal más a la derecha de la cadena de derivación Derivación por la izquierda: siempre se aplican las reglas de reescritura al símbolo no terminal más a la derecha de la cadena de derivación

19

Autómatas de Pila y Lenguajes Independientes de Contexto

07/03/2009

Ejemplo: Derivación por la derecha: 1. 2. 3. 4. 5. 6.

S S A A B B

AB A aAa λ Bb b

S

AB

ABb

ABbb

Abbb

aAabbb

aabbb

Derivación por la izquierda: S

AB

aAaB

aaB

aaBb

aaBbb

aabbb

20

Autómatas de Pila y Lenguajes Independientes de Contexto

07/03/2009

BNF La BNF es otra forma de especificar una gramática libre del contexto, y usa los siguientes símbolos: Símbolos no terminales entre <> Sustitución de → por ::=

Ejemplo: <sentenciafor>::=for<sentencia> Una gramática libre de contexto G, se dice que es ambigua, si existe alguna palabra perteneciente al lenguaje que genera que tenga más de un árbol de derivación.

Un lenguaje es intrínsecamente ambiguo cuando no existe ninguna gramática libre de contexto que lo genere que no sea ambigua.

21

Autómatas de Pila y Lenguajes Independientes de Contexto

Avram Noam Chomsky (7 de diciembre de 1928 en Filadelfia, Estados Unidos) es un lingüista, filósofo, activista, autor y analista político estadounidense. Es profesor emérito de Lingüística en el MIT y una de las figuras más destacadas de la lingüística del siglo XX, es sumamente reconocido en la comunidad científica y académica por sus importantes trabajos en teoría lingüística y ciencia cognoscitiva.

07/03/2009

22

Autómatas de Pila y Lenguajes Independientes de Contexto

07/03/2009

Respuestas 1. ¿Qué es un autómata de Pila? son dispositivos de computo que operan como una maquina de estados finitos, las cuales realizan un encadenamiento automático y continuo de operaciones capaces de procesar una información de entrada para producir otra de salida.

2. ¿Para que sirve la pila de los Autómatas? para almacenar información para recuperarla más tarde

3. ¿Qué es el principio de pre análisis? Técnica que permite a los autómatas de pila observar uno o varios símbolos más allá de donde se encuentra la cabeza lectora del autómata, pero sin leerlos realmente.

4. ¿Mencione el proceso de reconocimiento de una cadena? Se parte del estado inicial y la pila vacía Se lee la cadena símbolo a símbolo de izquierda a derecha Por cada símbolo leído se produce una transición desde el estado actual a otro a través de la flecha cuyo símbolo de entrada coincida con el símbolo leído, siempre y cuando la cabecera de la pila coincida con el símbolo de pila que figura a la izquierda del punto y coma La cabecera de la pila es sustituida en cada transición por el símbolo de la pila a la derecha del punto y coma en la etiqueta de la flecha El autómata puede realizar transiciones entre estados sin consumir símbolos de entrada o símbolo de pila a través de flechas en las que en el lugar correspondiente de la etiqueta aparezca el símbolo λ La cadena es reconocida si es posible que el autómata alcance un estado de aceptación, estando completamente con sumida la cadena de entrada

23

Autómatas de Pila y Lenguajes Independientes de Contexto

07/03/2009

5. ¿Qué significa un GIC? Gramática Independiente del Contexto

6. ¿Para que nos sirve un GIC? Para describir la sintaxis de los lenguajes de programación.

7. ¿Cuantos tipos de gramática existen según la clasificación de Chomsky y cuáles son? 1- Gramáticas regulares. 2- Gramáticas libres del contexto. 3- Gramáticas dependientes del contexto. 4- Gramáticas irrestrictas.

8. ¿A que se debe el nombre “Libre de Contexto”? se debe a que cada una de las producciones pueden ser aplicadas independientemente del contexto en donde aparezca un no terminal en una forma sentencial.

24

Autómatas de Pila y Lenguajes Independientes de Contexto

07/03/2009

Bibliografía • • • • •

http://dac.escet.urjc.es/~lrincon/uned/ta1/ta1-tema2.pdf http://148.202.148.5/cursos/cc209/teoriacomp/MODULO_4/Teoria_4_2.htm http://cnx.org/content/m16320/latest/ http://fisica.ciens.ucv.ve/etisc/2001/curso/Ce_iii_clase1.html http://156.35.94.1/asignaturas/aut.mat.dis/apuntes/Tema2-2005-2006V1.pdf

25