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 
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 
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 
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… !!! 
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 !!!!!
| Página siguiente |