Informatica

91

Ing. Fco. Ríos Acosta friosam@prodigy.net.mx

Autómatas Finitos

III AUTÓMATAS FINITOS.
3.1 INTRODUCCIÓN ........................................ ................ ............. ....... 92 93 102 105 127

3.2 AUTÓMATAS FINITOS DETERMINÍSTICOS

3.3 AUTÓMATAS FINITOS NO DETERMINÍSTICOS

3.4 AUTÓMATAS FINITOS Y EXPRESIONES REGULARES 3.5 EQUIVALENCIA ENTRE AFND Y AFD 3.6 OPTIMIZACIÓNDE 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 EJERCICIOSPROPUESTOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169

92

Ing. Fco. Ríos Acosta friosam@prodigy.net.mx

Autómatas Finitos

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ítulosanteriores, 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.

PROGRAMA FUENTE

ANALIZADORLÉXICO (a)

TOKENS

PROGRAMA FUENTE

AUTÓMATA FINITO (b)

TOKENS

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, suprogramació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.
CADENA X

AUTÓMATA FINITO

“SI” ( reconocimiento de X ) “NO” ( No reconocimiento o rechazo de X )

Fig. 3.2. Entrada y salida de un autómata finito.

93

Ing. Fco. Ríos Acosta friosam@prodigy.net.mx

Autómatas Finitos

Los autómatasfinitos 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 ididentificador en Pascal es mostrado
en la fig. 3.3. La definición regular es : Letra Dig Sub Id

⇒ ⇒ ⇒ ⇒

[ A-Za-z ] [ 0-9 ] _ Letra ( Letra | Dig | Sub ) *
Inicio Letra

Letra

0

1
Dig

Sub

Fig 3.3 AFD para el token id en Pascal.

94

Ing. Fco. Ríos Acosta friosam@prodigy.net.mx

Autómatas Finitos

Un autómata es una representación gráfica que muestra el proceso dereconocimiento de una cadena de entrada. La simbología utilizada es simple :
n

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.

a

inicio s

f

De acuerdo a la notación anterior,...