Agregar a favoritos      Ayuda      Português      Ingles     

Autómatas finitos

Enviado por FRANCISCO RIOS ACOSTA



Partes: 1, 2, 3, 4


Monografias.com
91 III AUTÓMATAS FINITOS. 3.1 INTRODUCCIÓN ........................................ 92 3.2 AUTÓMATAS FINITOS DETERMINÍSTICOS ................ 93 3.3 AUTÓMATAS FINITOS NO DETERMINÍSTICOS ............. 102 3.4 AUTÓMATAS FINITOS Y EXPRESIONES REGULARES ....... 105 3.5 EQUIVALENCIA ENTRE AFND Y AFD .................... 127 3.6 OPTIMIZACIÓN DE AFD’s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 3.7 PROPIEDADES DE LOS LENGUAJES ACEPTADOS POR UN AUTÓMATA FINITO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167 3.8 DETERMINACIÓN DE LENGUAJES REGULARES Y NO REGULARES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168 3.9 EJERCICIOS PROPUESTOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
Monografias.com
92 Palabras clave : Automátas finitos determinísticos, no deterministicos, AFD,AFND, reglas de Thompson, algoritmo de construcción de subgrupos, algoritmo de particiones.AFD óptimo, AFD reducido. 3.1 INTRODUCCIÓN. Habíamos establecido en los capítulos anteriores, que un analizador léxico reconocía tokens, mediante un monitoreo de izquierda a derecha del programa fuente. Para hacer esta tarea menos difícil, utilizábamos las expresiones regulares para la especificación de los patrones o reglas que cumplen los tokens. Los autómatas finitos son las herramientas empleadas como reconocedores de tokens, fig. 3.1. (b) Fig. 3.1 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 de cadenas 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, fig. 3.2. AUTÓMATA FINITO CADENA X “SI” ( reconocimiento de X ) “NO” ( No reconocimiento o rechazo de X ) Fig. 3.2. Entrada y salida de un autómata finito. ANALIZADOR LÉXICO (a) AUTÓMATA FINITO PROGRAMA FUENTE PROGRAMA FUENTE TOKENS TOKENS
Monografias.com
93 Los autómatas finitos se clasifican en : a) Determinísticos. b) No Determinísticos. 3.2 AUTÓMATA FINITO DETERMINÍSTICO (AFD). Es un modelo matemático que consiste de : • Un conjunto de estados, denominado S. • Un conjunto (alfabeto) de símbolos de entrada, denominado ?. • Una función de transición move que mapea un par P ( s , a ) a un estado t. s y t son estados contenidos en S, a es un símbolo de entrada. • Un estado de inicio, denotado por s0. • Un conjunto de estados de aceptación (finales), denotado por F. Además, un autómata finito determinístico AFD debe cumplir con las siguientes características : a) No hay transiciones etiquetadas por ?. b) Para cada estado s y un símbolo de entrada a, existe a lo más un arco etiquetado por a saliendo de s. Ejemplo 3.1. El AFD que reconoce al token id identificador en Pascal es mostrado en la fig. 3.3. La definición regular es : Letra Dig Sub Id ? ? ? ? 0 1 [ A-Za-z ] [ 0-9 ] _ Letra ( Letra | Dig | Sub ) * Letra Inicio Letra Dig Fig 3.3 AFD para el token id en Pascal. Sub
Monografias.com
94 Un autómata es una representación gráfica que muestra el proceso de reconocimiento de una cadena de entrada. La simbología utilizada es simple : Un círculo representa un estado n, donde n es un número natural o bien una letra, generalmente. Un arco representa la lectura de un símbolo a en la entrada. Transición entre estados. Estado de inicio s. s es generalmente 0 (cero). Estado de aceptación f. 2. del AFD. El conjunto o alfabeto de símbolos de entrada, se obtiene de los arcos a ? = { A, B, ... , Z, a, b, ... , z, 0, 1, ... , 9 , _ } Letra Dig Sub Es decir el alfabeto ? es el conjunto de las letras mayúsculas y minúsculas, unidas a los dígitos y el símbolo de subrayado ( _ ). 3. La función de transición move es realmente una tabla de transición, donde los renglones son los estados y las columnas son símbolos de entrada. s n a inicio f LyA De acuerdo a la notación anterior, dispongámonos a obtener los componentes del AFD de la fig. 3.3. 1. El conjunto de estados del autómata AFD es : S = { 0,1 } Dos estados... !!!
Monografias.com
95 Ing. Fco. Ríos Acosta En las columnas debemos ubicar a todos los posibles símbolos del alfabeto que pueden ocurrir, al efectuar una lectura en la entrada (cadena). En nuestro caso son: Letra, Dígito y Subrayado. Autómatas Finitos LyA Símbolos en la entrada Estados Fig. 3.4 Función move para el AFD que reconoce al token id en Pascal. La construcción de la tabla de transición -función move- se inicia identificando los estados que tienen al menos un arco que “salga” de ellos. Para nuestro ejemplo el estado 0 (cero) tiene un arco etiquetado por Letra que “sale” de él, y el estado 1 tiene 3 arcos: Letra, Dig y Sub. Los estados que tengan esta característica son añadidos como los renglones en la tabla. Sólo los estados que tengan arcos saliendo de ellos, ... eeh !!!!!
Partes: 1, 2, 3, 4

Página siguiente 

Comentarios


Trabajos relacionados

Ver mas trabajos de Programacion

 

Nota al lector: es posible que esta página no contenga todos los componentes del trabajo original (pies de página, avanzadas formulas matemáticas, esquemas o tablas complejas, etc.). Recuerde que para ver el trabajo en su versión original completa, puede descargarlo desde el menú superior.


Todos los documentos disponibles en este sitio expresan los puntos de vista de sus respectivos autores y no de Monografias.com. El objetivo de Monografias.com es poner el conocimiento a disposición de toda su comunidad. Queda bajo la responsabilidad de cada lector el eventual uso que se le de a esta información. Asimismo, es obligatoria la cita del autor del contenido y de Monografias.com como fuentes de información.

Iniciar sesión

Ingrese el e-mail y contraseña con el que está registrado en Monografias.com

   
 

Regístrese gratis

¿Olvidó su contraseña?

Ayuda