Autómatas Finitos

2 Autómatas Finitos

2.1 AUTÓMATAS FINITOS DETERMINISTAS (AFD).
2.1.1

DEFINICIÓN DE AFD.

Un autómata finito determinista es una quíntupla que denotaremos de manera genérica
por M=(Q,Σ,q0,δ,F) donde:
Q es un conjunto finito cuyos elementos llamaremos estados.
Σ es un alfabeto que llamamos alfabeto de entrada.
q0∈Q es un estado señalado que llamamos estado inicial.
F es un subconjuntode Q no vacío, cuyos elementos llamamos estados finales.
δ es una aplicación de Q×Σ→Q , que llamamos función de transición.
La función de transición es la verdadera clave de la máquina. Obsérvese que es una
aplicación, así cada pareja posible formada por un estado y un símbolo del alfabeto debe
tener una imagen y sólo una, es decir δ(q,a)∈Q, cualquiera que sean q∈Q y a∈Σ.
Ejemplos:
19
©Inmaculada Luengo

2. Autómatas Finitos

2.1 Autómatas Finitos Deterministas (AFD)

Sea M1 = (Q, Σ, δ, q0,F) donde Q={p,q,r}, Σ={a,b}, Sea p el estado inicial, F={r} y δ
definida como sigue:
δ(p,a)=q

δ(p,b)=r

δ(q,a)=p

δ(q,b)=q

δ(r,a)=r

δ(r,b)=r

Tabla 2.1. Función de transición de M1.

Según nuestra definición M1 es un AFD.
Para visualizarlo de alguna forma imaginemosuna especie de circuito electrico con
tantas bombillas como estados, las correspondientes a los estados finales de color verde,
las demás amarillas. Sobre una cinta de entrada escribimos una palabra con símbolos del
alfabeto de entrada. Al poner a funcionar la máquina se enciende la bombilla
correspondiente al estado inicial. A partir de ese momento se procesa el símbolo actual
en la cinta deentrada transitando al estado definido en cada momento por la función de
transición hasta que la palabra de la entrada haya sido leido completa.
Si la palabra a procesar fuese aabbab, se enciende el estado p inicial y a continuación
qprrrr. El estado que queda encendido es r que es final. Si la palabra a procesar fuese
abbb la secuencia de estados sería pqqqq.

2.1.2

REPRESENTACIÓN DE UNAFD.

Tenemos dos maneras de representar un AFD
Con una tabla:
Se ponen tantas filas como estados, y tantas columnas como símbolos forman el
alfabeto. Marcamos el estado inicial con una flecha de entrada y cada uno de los
estados finales con un asterisco. En el cruce de la fila marcada con el estado q y
la columna marcada con el símbolo a del alfabeto ponemos el estado δ(q,a).
Con undiagrama:
Cada estado no final se representa con un círculo; cada estado final se representa
con un doble círculo; se señala el estado inicial con una flecha entrando, sin

20
© Inmaculada Luengo

2. Autómatas Finitos

2.1 Autómatas Finitos Deterministas (AFD)

etiqueta; por cada transición δ(q,a)=t se dibuja una flecha dirigida del estado de
partida q al de llegada llegada t etiquetada aEjemplos:
La máquina M1 del ejemplo se representa con una tabla
δ

a b

→p q r
q

p q

*r

r

r

Tabla 2.2. Autómata finito determinista M1.

O bien se representa con un diagrama

Fig. 2.1 Autómata finito determinista M1.

Observemos que cada una de ambas representaciones contiene toda la información del
autómata.

2.1.3

DIAGRAMAS INCOMPLETOS: ESTADO DE ABSORCIÓN.Con frecuencia nos encontramos AFDs como el M2 siguiente.

Fig. 2.2 autómata finito determinista M2.

21
© Inmaculada Luengo

2. Autómatas Finitos

2.1 Autómatas Finitos Deterministas (AFD)

Si observamos con un poco de atención vemos que la transición δ(p,1) no está
representada, lo que contradice la definición de AFD puesto que hemos afirmado que δ
es una aplicación. Lo que ocurreen realidad es que la máquina no ha sido
completamente dibujada, por comodidad y claridad. Debemos entender que todas las
transiciones que falten en el diagrama de un AFD van a un único estado no final, que
llamamos genéricamente estado de absorción. Así el diagrama completo de M2 es:

Fig.2.3. Autómata finito determinista M2 con el estado de absorción.

El estado s es el estado de...