Cátedra Compiladores
Facultad de Ingeniería – Universidad Católica de Salta
AUTÓMATAS FINITOS
Los autómatas finitos son entes o máquinas abstractas que se estudian desde dos puntos de
vista: como dispositivos capaces de determinar la pertenencia de una cadena de símbolos a un
lenguaje determinado y como traductores de una cadena en otra. En este último caso los au-
tómatas están computando una función.
Se puede imaginar un Autómata Finito como una máquina capaz de leer símbolos de una
cinta y según el estado corriente cambiar de estado hasta terminar la cinta. Consta, entonces
de una cinta de entrada y un control que mantiene el estado actual y posee una cabeza lecto-
escritora que luego de leer un símbolo se mueve hacia la derecha y es capaz de decidir dado
el estado corriente y el símbolo leído cual es el próximo estado.
La memoria central del autómata queda determinada al momento del diseño, ya que el
autómata “recuerda” a través de sus estados. El conjunto de situaciones, es decir, de estados
que registra el autómata es finito y queda determinado en su diseño. Esta es la memoria del
autómata, ya que “recuerda” a través de sus estados. Entre los estados siempre podemos dis-
tinguir el inicial y los finales o aceptadores. Los estados finales determinan la aceptación de
la cadena cuando ésta se terminó de leer. Eventualmente el estado inicial puede ser también
aceptador.
Ya que los estados le permiten al autómata “recordar” situaciones que se desea diferenciar,
es crucial en su diseño saber distinguir el conjunto de situaciones mínimas que se desea con-
trolar. Debido a que el conjunto de estados es finito, en cada momento el autómata estará en
alguno de ellos.
Autómatas Finitos Reconocedores
Para ver la importancia de estos autómatas, nótese que la fase de análisis léxico de un
compilador está basado en un Autómata Finito, pues son usados para describir el proceso de
reconocimiento de patrones en el texto de entrada.
Un autómata finito es una quíntupla M = (S, , , s0, F) donde:
S: es un conjunto de estados, S
: es el alfabeto de entrada
s0: es el estado inicial , s0 S
F: es el conjunto de estados finales o aceptadores, F S
: S S es la función de próximo estado o de transición.
Ejemplo
Sea el autómata finito M que reconoce el lenguaje de los identificadores válidos de un
lenguaje de programación L. Recuerde que, según la definición, un identificador es una letra
seguida de una sucesión de letras o dígitos.
Cátedra Compiladores
Facultad de Ingeniería – Universidad Católica de Salta
M = (S, , , F, s0)
S = {s0, s1, s2}
= {a .. z, 0 .. 9}
F = {s1}
Nota: Si bien el alfabeto indica
letra dígito en forma individual cada letra y dí-
s0 s1 s2 gito, por simplicidad en la tabla de es-
s1 s1 s1 tados se indica sólo una columna por
s2 s2 s2 las 28 letras y otra para los dígitos.
Se puede extender la definición de de un autómata finito M de símbolos a cadenas, es
decir, (s0, w), donde el estado resultante es el que se obtiene de aplicar a partir del estado
inicial y a cada símbolo de la cadena. Entonces: : S * S es la función de próximo
estado o transición.
(si, ) = si
(si, ax) = ((si, a), x) a , x *
Para el ejemplo anterior, sea id1 un identificador de L:
’(s0, id1) = s1 pues:
’(s0, id1) = ’((s0, i), d1) = ’(((s0, i), d), 1) = ’((((s0, i), d), 1), ) =
’(((s1, d), 1), ) = ’(( s1, 1), ) = ’( s1, ) = s1
Se dice que el autómata finito M acepta o reconoce la cadena w * si (s0, w) = q, donde
q F, es decir si M comenzando en el estado inicial s0, lee la cadena w de izquierda a derecha
y termina en un estado final o aceptador.
Aplicación de grafos dirigidos para representar la función de próximo estado
Un grafo dirigido es una terna (N, A, F) donde N es el conjunto de vértices o nodos. A es
un conjunto de arcos. F es la función que asocia a cada arco a A con un par ordenado de
vértices.
Los grafos dirigidos se utilizan para representar autómatas finitos y se llaman Diagramas
de estados o Diagrama de transiciones. Las convenciones son las siguientes:
- Existe un nodo n N del grafo por cada estado s S
- Existe un arco a A tal que F(a) = (si, sk) ⇔ (si, a) = sk, donde si, sk S, a
- Los estados finales se distinguen con un doble círculo.
- El estado inicial se marca con . Debe notarse que cada arco puede tener más de un
rótulo.
Cátedra Compiladores
Facultad de Ingeniería – Universidad Católica de Salta
Ejemplo:
Lenguaje de los identificadores. Los nodos del grafo son s0, s1, s2. El estado inicial s0, el
final s1.
l, d
l
s1
s0
d s2 l, d
