Autómatas Finitos

1
 Definición informal de autómata
• Máquina: es una secuencia o ciclo de acciones.
• Autómata finito: es un modelo matemático de una máquina el
cual tiene un conjunto finito de estados y su “control” se mueve de
estado a estado (transiciones).
– Autómata determinista: el autómata no puede estar en más de un
estado a la vez. Las transiciones se efectúan en respuesta a “entradas” o
“estímulos” externos. Estas entradas son símbolos de un alfabeto.
– Autómata no-determinista: el autómata puede estar en varios estados
al mismo tiempo. Las transiciones de un estado a otro pueden ocurrir de
manera espontánea, es decir, en respuesta a la palabra vacía  como entrada.
• Veremos que un autómata no-determinista se puede
convertir en un autómata determinista equivalente
(¿?) el cual puede ser “ejecutado” por una
computadora convencional.
2
 Caricatura de un autómata finito

Cinta de
a b a b b a entrada
Cabeza q0
lectora Control
qn q1 Luz de
aceptación
q2
qi
q4 q3

3
 Definición formal de un AFD

Un Autómata Finito Determinístico (AFD) es un

quinteto (K, , , s0, F) donde
• K es un conjunto finito no-vacío de estados.
•  es el alfabeto de entrada (conjunto finito no-vacío de
símbolos).
•  : K    K es la función de transición.
• s0  K es el estado inicial.
• F  K es el conjunto de estados finales.
Determinístico: para cada combinación de sK y a, la
función  especifica uno y sólo un estado de transición.
4
 Notación gráfica
• Estado inicial: >
• Estado final:
• Transiciones: a
a
a
q1

> q0 b
b

a b
q2

5
 Notaciones
• Un AFD puede considerarse como un grafo
dirigido G = (V, E)
–V=S
– E = {((s, a), t) | s, t  S, a  y (s,a) = t}
• La función de transición puede expresarse
como una tabla. Por ejemplo

 a b
q0 q1 q2
q1 q1 q1
q2 q0 q2
6
 ¿Para que sirven los AFD?
• Si al “procesar” una palabra completa el estado al que se llega es
uno de los estados finales, entonces decimos que el AFD acepta la
palabra.
Un poco más formalmente: extendemos la función  a una función 
para cubrir cadenas en lugar de sólo letras. Así, si s es un estado y
w es una cadena, entonces (s, w) es el estado en el que se termina
cuando se empieza en s después de procesar en orden todas las
letras de la palabra w. La función  es llamada función de
transición extendida.
• Decimos que un AFD M = (K, , , s0, F) acepta una palabra w si
y sólo si (s0, w)  F.
• Decimos que un AFD M = (K, , , s0, F) rechaza una palabra w si
y sólo si (s0, w)  F.
• El lenguaje aceptado por una máquina M = (K, , , s0, F) es el
conjunto de palabras aceptadas por dicha máquina. El lenguaje
aceptado por M se denota por L(M), es decir,
L(M) = {w* | (s0, w)  F} 7
Diseño de Autómatas Finitos

8
 Ejemplo

q0 q1 0

0 1

Este AFD acepta palabras con un número impar de 1’s

9
 Diseño de AFD’s
• Definir un AFD que acepte palabras que
cumplan ciertas especificaciones.
– Correcto: que las palabras aceptadas por el AFD cumplan
las especificaciones, es decir, que no “sobren” palabras.
– Completo: que toda palabra que cumpla las
especificaciones sea aceptada por el AFD, es decir, que no
“falten” palabras.
• Ejemplo: AFD que acepte palabras sobre {a, b} que no tengan
varias a’s seguidas. a a
El AFD de la figura no es q1
correcto porque acepta “baa”,
pero no acepta “ba”. > q0 b
b
a q2 b
10
 ¿Cómo diseñar un autómata finito

• Por “ensayo y error” no es adecuado.

• “Póngase en los zapatos” del autómata que quiere
diseñar.
– Para cada símbolo leído, saber si la cadena es aceptada o no,
por si la cadena termina ahí.
– Decida que información es crucial “recordar”, es decir,
cuales serían los estados del autómata.
– Asignar transiciones, estado inicial y estado(s) final(es).

11
 Ejemplo
• Diseñar un AFD que acepte todas las palabras sobre {0, 1} que
tengan un número impar de 1’s.
– No se requiere saber cuantos 1’s se han leído sino sólo si llevamos un número
par o impar de 1’s. Esta respuesta permanece igual si enseguida leemos un 0 y
cambia si leemos un 1.
– Representar esto como una lista de posibilidades y asignar un estado a cada
posibilidad: a) par hasta ahorita. B) impar hasta ahorita.
– Asignar las transiciones.
– Definir el estado inicial, el que corresponde a la palabra nula .
– Definir el estado final, el que corresponde a palabras de longitud impar.

qpar qimpar 0

0
1
12
 Ejercicio
Diseñar un AFD que acepta las palabras con un
número par de a’s y un número par de b’s.
• La función de los estados es la de contar el número de
a’s y el número de b’s, pero contarlas módulo 2, es
decir, los estados servirán para recordar si el número
de a’s que se han leído es par o impar y también
recordar lo correspondiente para el número de b’s. Hay
cuatro estados.
– q0: tanto el número de a’s como de b’s que se han leído es par.
– q1: el número de a’s es par pero el número de b’s es impar.
– q2: el número de a’s es impar pero el número de b’s es par.
– q3: el número de a’s es impar y el número de b’s es impar.

13
 Ejemplo
a

(0,0) (1,0)

a
b b b b
a

(0,1) (1,1)

Acepta cadenas con un número par de a’s

y un número par de b’s.
14
 Un ejemplo más

• Construir un autómata finito determinista que reconozca el lenguaje

sobre {0, 1} que consiste de las palabras que terminan con 1, es decir,
(0 + 1)*1.

0 1
1
A B
0

15
 Ejemplos
• Diseñar un AFD que acepte exactamente el
lenguaje sobre {0, 1} en que las palabras no
comienzan con 00.
0,1

q0 0 q1 0 q2

1 1

q3

0,1

16