• Author / Uploaded
• KlismanJbj

Citation preview

Automata Finito Determinista Un Automata Finito Determinista (AFD) es una maquina de estados que actua como reconocedor para un lenguaje regular. Formalmente se define como una 5-tupla (Q, Vt, q0, δ, qF) donde: Q es un conjunto finito de estados Vt es el alfabeto de entrada q0 es el estado inicial δ son las reglas de transición Q X Vt -- > Q qF es el estado final o conjunto de estados finales

Representación como grafo Ejemplo: Para L = { a+ b+} tenemos el siguiente autómata, representado como grafo

Dada la cadena candidata aaabb Se inicia el reconocimiento partiendo del estado inicial q0, con el primer a pasamos a q1, en el cual permaneceremos con los siguientes símbolos a, al llegar el primer símbolo b pasamos a qF, donde permaneceremos con los siguientes b. Dada la cadena candidata bab, partimos de q0 y al llegar el primer símbolo b no podemos pasar a q1 (solo se pasa a q1 con a). En este caso al no poder realizar la transición, se realiza una transición automática a un estado qE, el cual es el estado de error, esto implica que dicha cadena candidata no pertenece al lenguaje. Puede existir un problema si por ejem tenemos la cadena candidata aaba porque partiendo de q0, con el 3er símbolo llegamos a qF, pero al llegar el 4to símbolo, a, ya no podemos quedarnos en qF y pasaríamos al estado de error, es decir habiendo llegado a qF ya no podemos permanecer en él (Habiendo reconocido, luego no reconocemos). Para evitar esto podemos considerar el delimitador $, el cual representa el ”fin de cadena”, asi tenemos:

Lenguajes y Compiladores / Jaime Pariona Quispe

Representación como reglas de transición Usando el ejemplo anterior, podemos representar el mismo autómata a través de las reglas de transición: δ : ( q0, a ) --- > q1 ( q1, a ) --- > q1 ( q1, b ) --- > q2 ( q2, b ) --- > q2 ( q2, $ ) --- > qF

Representación como Matriz de Transición También lo podemos representar como una Matriz de Transicion (MT)

q0 q1 q2

a q1 q1 -

b q2 q2

$ qF

Determinista y No Determinista El autómata es determinista (AFD) cuando para cada símbolo es posible solo una transición a un estado.

Es no determinista (AFND), cuando con el mismo símbolo es posible hacer una transición a 2 o más estados diferentes.

Lenguajes y Compiladores / Jaime Pariona Quispe

Algoritmo de Implementacion Podemos usar el ejemplo anterior para mostrar las posibles formas de implementación: 1. Usando Reglas de transición #define QF 100 #define QE -1 q = 0; token = scanner(); mientras ( q !=QF && q!=QE ) { caso ( q ) { 0 : si (token == ‘a’) q = 1; sino q = QE; 1 : si (token == ‘a’) q = 1; sino si (token == ‘b’) q = 2; sino q = QE; 2 : si (token == ‘b’) q = 2; sino si (token == ‘$’) q = QF; sino q = QE; } token = scanner(); } si (q==QF) reconoce(); sino error(); Lenguajes y Compiladores / Jaime Pariona Quispe

2. Usando Matriz de Transición #define QF 100 #define QE -1 q = 0; token = scanner(); mientras ( q !=QF && q!=QE ) { q = MT ( q, token) token = scanner(); } si (q==QF) reconoce(); sino error();

Ejemplos: 1. L = { numero binario par} { (0│1)*0} 2. L = { numero binario que empieza y termina en digitos diferentes} { 0 (0│1)* 1 │ 1 (0│1)*0 } 3. L = { nombre de variable } { (│)* } 4. L = { declaracion de funcion en C} { ID ‘(‘ [ ID ( , ID)* ]

$

‘)’ }

5. L = { numero binario que no contiene dos digitos 1 consecutivos } 6. L = { numero binario tal que si empieza en 0 tiene longitud par, y si empieza en 1 tiene longitud impar} 7. L = { numero real con parte entera par y parte fraccionaria impar } { * . + } 8. L = {numero real con signo y posible forma exponencial }, ejm +32.475E+3

Lenguajes y Compiladores / Jaime Pariona Quispe

9. L = { declaracion de variable en Pascal} Ejm. VAR a, b : integer; x : real BEGIN 10. L = { sentencia INSERT de SQL} Ejm. Insert into tabla1 values (32, ‘abc’) AFND con λ Un automata finito sera tambien AFND si es que tiene transiciones λ Ejm. L = { (a│b)* b} El AFND será:

Usando transiciones λ sera

Lenguajes y Compiladores / Jaime Pariona Quispe

TIP: Software para diagramacion de AFDs:

http://www.jflap.org/

JFLAP is a package of graphical tools which can be used as an aid in learning the basic concepts of Formal Languages and Automata Theory.

----- EOF ---http://www.di-mare.com/adolfo/cursos/2009-2/pp-A71925-A73605-A73869-A75755.pdf http://webdiis.unizar.es/asignaturas/TC/wp/wp-content/uploads/2012/09/121008MinimAFDs.pdf http://www2.dis.ulpgc.es/~mluengo/automatas/teoria/tema2.pdf

Lenguajes y Compiladores / Jaime Pariona Quispe