redes

91

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

Autómatas Finitos

III
AUTÓMATAS FINITOS.
3.1 INTRODUCCIÓN

........................................

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ÓN DE AFD’s

92.......

....................

93
102
105
127

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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

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í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.PROGRAMA
FUENTE

ANALIZADOR
LÉXICO

TOKENS

(a)
PROGRAMA
FUENTE

AUTÓMATA
FINITO

TOKENS

(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.
Unautó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.
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.

Ing. Fco. Ríos Acostafriosam@prodigy.net.mx

93

Autómatas Finitos

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 tson 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
asaliendo 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

⇒
⇒
⇒
⇒

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

Letra

Letra

Inicio

0

1
Dig

Fig 3.3 AFD para el token id en Pascal.

Sub

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

94

AutómatasFinitos

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.

n

a

Un arco representa la lectura de un símbolo a en la entrada. Transición entre
estados.

inicio
s

f

Estado de inicio s. s es...