Automatas finitos y lenguajes regulares

qwertyuiopasdfghjklzxcvbnmqwertyui opasdfghjklzxcvbnmqwertyuiopasdfgh jklzxcvbnmqwertyuiopasdfghjklzxcvb AUTÓMATAS FINITOS Y nmqwertyuiopasdfghjklzxcvbnmqwer LENGUAJES REGULARES tyuiopasdfghjklzxcvbnmqwertyuiopas dfghjklzxcvbnmqwertyuiopasdfghjklzx NAARA GUIZAR PÉREZ 5 “F“ cvbnmqwertyuiopasdfghjklzxcvbnmq wertyuiopasdfghjklzxcvbnmqwertyuio pasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbn mqwertyuiopasdfghjklzxcvbnmqwerty uiopasdfghjklzxcvbnmqwertyuiopasdf ghjklzxcvbnmqwertyuiopasdfghjklzxc vbnmqwertyuiopasdfghjklzxcvbnmrty uiopasdfghjklzxcvbnmqwertyuiopasdf ghjklzxcvbnmqwertyuiopasdfghjklzxc
26/09/2011

Índice

Introducción

Autómatas finitos………………………………………………………………………………………………. 4

Autómata finitos no deterministicos………………………………………………………………… 4

Autómatafinito determinístico………………………………………………………………………… 5

Expresiones regulares ……………………………………………………………………………………… 6

Conclusión

Bibliografía

Página 2

Introducción
Los autómatas finitos son las herramientas empleadas como reconocedores de tokens,

a) Análisis léxico, b) Interior del analizador léxico. Un autómata finito es capaz de reconocer un conjunto regular, es decir, un conjunto decadenas denotado por cualquier expresión regular. Recordemos que una expresión regular denota a un lenguaje regular. Un autómata finito es un reconocedor para un lenguaje, su programación no es una tarea compleja, su entrada es una cadena x y responde “si” si x es una sentencia del lenguaje, “no” de otra manera

Entrada y salida de un autómata finito Los autómatas finitos se clasifican en: a)Determinísticos. b) No Determinísticos.

Página 3

AUTÓMATAS FINITOS Un autómata finito es un conjunto de nodos y aristas que representan trayectorias para generar una expresión bajo un alfabeto. Un diagrama de transición es un autómata finito. Los autómatas finitos se clasifican en:
o o

Autómatas finitos no determinísticos. NFA Autómatas finitos determinísticos. DFA

Autómata Finito NoDeterminístico Un NFA es un modelo matemático que consiste de: 1.- Un conjunto de estados. 2.- Un conjunto de símbolos de entrada. 3.- Una función de transición que corresponde pares estado-símbolo a conjuntos de estados. 4.- Un estado So que denota como el estado inicial. 5.- Un conjunto de estados F que denotan los estados de aceptación o finales. Un NFA no tiene restricciones para que exista masde una transición con el mismo nombre a diferentes estados, por lo que en una representación tabular no es posible determinar de manera única el estado destino para un símbolo determinado. Por ejemplo, el siguiente diagrama representa la expresión (a | b)* a b b

No podemos determinar a qué estado se avanza del estado 0 con el símbolo a; puede ser al propio 0 o al 1 pero ¿bajo qué condición? Noestá determinado. Incluso podría existir transiciones sin ninguna restricción, que se denominan transiciones épsilon porque no requieren un símbolo determinado ocurra para
Página 4

realizarse. Nuevamente, esto se vuelve indeterminado en una representación tabular. Autómata Finito Determinístico Un DFA es un caso especial de NFA en el que ningún estado tiene transiciones para diversos estadosbajo el mismo símbolo y no se permiten transiciones épsilon. Los diagramas de transición son autómatas determinísticos. Por ejemplo, el DFA de (a | b)* a b b puede ser:

Que podría ser muy aproximado al diagrama de transición que construiríamos para la expresión. Para llegar de la expresión regular al autómata determinístico se emplea el método de Thompson que permite hacer la transformación ypreparar la construcción del analizador de léxico. - Autómatas finitos: reconocen lenguajes regulares. - Aplicación más importante: construcción de compiladores (analizadores léxicos). ANÁLISIS LÉXICO - Token: elemento del lenguaje (palabra reservada, nombre de variable, punto y coma, Constante, etc.). - Marcas de fin de cadena: delimitan los tokens. Diagrama de transición de estados - Colección...