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 |