Automatas Finitos

Compiladores. Guía 2

1

Facultad:
Ingeniería
Escuela:
Computación
Asignatura: Compiladores

Tema: Autómatas de Estado Finitos
Contenido
En esta guía se aborda la aplicación de los autómatas en el
campo de los procesadores de lenguaje, haciendo énfasis en
los Autómatas de Estado Finito.

Objetivos Específicos
Conocer las características básicas de un Autómata
Estado Finito.
Crear algunassecuencias de cadenas evaluadas por
Autómata Finito en Jflap, e implementarlos en C++.

de
un

Material y Equipo
Guía No 2.
Computadora con Dev-C++ y

el simulador Jflap.

Introducción Teórica
Aplicación de los autómatas en los procesadores de lenguaje

Guía 3

La tarea de comprobar si una sentencia pertenece o no a un
determinado
lenguaje se encomienda a los autómatas. En el
Guía 4
campo
de
estudio
delos
traductores,
compiladores,
procesadores e intérpretes los autómatas se utilizan como
fía
reconocedores
de lenguajes, que dada una cadena de símbolos
indican si dicha cadena pertenece o no al lenguaje.
Una cadena pertenece a un lenguaje si el autómata reconocedor
de dicho lenguaje lo toma como entrada, y partiendo del
estado inicial
transita a través de varias configuraciones
hasta que alcanza elestado final
Autómatas finitos
Un autómata finito es un conjunto de nodos y aristas que
representan trayectorias para generar una expresión bajo un

2

Compiladores. Guía 2

alfabeto. Un diagrama de transición es un autómata finito.
Existen dos tipos autómatas finitos, los cuales son:
Autómatas finitos deterministas (AFD)
Autómatas finitos no deterministas (AFND)
Autómatas finitos deterministas(AFD)
Definición. Una máquina de estados finitos M es un quíntuplo
(K, Σ, δ, s, F), donde:
K es conjuntos de estados.
Σ es el alfabeto de entrada.
δ : K X Σ → K, es la función de transición, que
de un estado y un símbolo del alfabeto obtiene
estado.
s ∈ K es el estado inicial.
F ⊆ K es un conjunto de estados finales.
δ : K X Σ → K, es la función de transición, que
de un estado y un símbolo delalfabeto obtiene
estado.

a partir
un nuevo

a partir
un nuevo

Ejemplo:

Figura 1. Autómata Finito Determinista
Este autómata finito determinista puede ser expresado
formalmente como: M = (K, Σ, δ, q0, F)
K = {q0, q1, q2}
Σ = {a, b}
δ = {((q0, a), q1), ((q0, b), q2), ((q1, a), q1), ((q1,
b), q1), ((q2, a), q0), ((q2, b), q2)}
F = { q1, q2 }
IMPORTANTE: Para que un AFD sea válido, el número detransiciones que salen de cada estado debe ser igual a la
cantidad de caracteres del alfabeto, puesto que δ es una
función que está definida para todas las entradas posibles.

Compiladores. Guía 2 3

Para el AFD anterior, el alfabeto es {a, b} de cada estado
deben salir exactamente dos transiciones, una con a y otra
con b.
Otra condición es que debe tener exactamente un estado
inicial. En cambio, lacantidad de estados finales puede
ser cualquiera, inclusive cero, hasta un máximo de |K| (la
cantidad de estados).
Autómatas finitos no deterministas (AFND)
Una extensión de los AFD’S es la de permitir que de cada
estado o nodo del diagrama de estados salga un número de
flechas mayor o menor que |Σ|. Así se puede permitir que
falte la flecha correspondiente a alguno de los símbolos del
alfabeto, obien que haya varias flechas que salgan de un
solo nodo con la misma etiqueta. Inclusive se permite que las
transiciones tengan como etiqueta palabras de varias letras o
hasta la palabra vacía.
Definición. Un autómata finito no determinista es un
quíntuplo (K, Σ, Δ, s, F), donde K, Σ, s y F tienen el mismo
significado para el caso de los AFD y Δ, llamada la relación
de transición, es un subconjuntofinito K X Σ* X K.
Ejemplo. Verificar si la palabra baabbaba es aceptada por el
autómata finito no determinista siguiente:

Figura 2. Autómata Finito No Determinista
Solución. La palabra baabbaba puede ser dividida en cuatro
pedazos: p1 = b, p2 = a, p3 = abbab y p4 = a, cuya
concatenación produce la palabra original. Ahora bien,
podemos
seguir
la
siguiente
secuencia
de
estados
(trayectoria) en...