Autómatas Finitos
1
Ejemplo de una máquina expendedora
de periódicos (que no dá cambio)
d
30
q
n
d
25
q
n: niquel (5c)
d: dime (10c)
q: quarter (25c)
n
d
20
q
n
d
15
q
n
d
10
q
n
d
5 q
n
n,d,q
0
El periódico cuesta 30 centavos
2
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.
3
Caricatura de un autómata finito
a
b
Cabeza
lectora
a
b
b
Cinta de
entrada
a
q0
Control
q1
qn
Luz de
aceptación
q2
qi
q4
q3
4
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.
5
Notación gráfica
• Estado inicial: >
• Estado final:
• Transiciones: a
a
a
q1
> q0
b
b
a
q2
b
6
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
7
¿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,
8
L(M) = {w* | (s0, w)  F}
Ejemplo
1
q0
0
q1
0
1
Este AFD acepta palabras con un número impar de 1’s
9
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.
10
Ejemplo
a
(1,0)
(0,0)
a
b
b
b
b
a
(0,1)
(1,1)
a
Acepta cadenas con un número par de a’s
y un número par de b’s.
11
Ejemplo
b
S0
b
a
S1
a
S5
a,b
b
S4
b
S2
a
a
b
a
S3
Acepta palabras que contienen ababb
12
Ejemplo
b
S0
a
S1
a
S5
b
b
a
S4
b
a
S2
a,b
S3
a,b
Acepta palabras que contienen ababb o abbbb
13
Ejemplos
a
M1
q0
a,b
b
q1
b
q2
a
Acepta palabras que contienen bb,
es decir (a+b)*bb (a+b)*.
b
M2
q0
a,b
a
q1
a
q2
b
Acepta palabras que no contienen aa,
es decir (b+ab)*(a+).
14
¿M1  M2?
a
a
a
q1
q2
b
q3
a
a
q0
b
b
b
q4
b
q5
a,b
Acepta palabras que contienen bb o no contienen aa
es decir (a+b)*bb (a+b)* + (b+ab)*(a+).
15
Descargar

Autómata Finito Determiníístico AFD