Minimización Autómata de
Moore
Carolina Cáceres Ahumada
27 abril, 2010
Autómatas
• Mealy: asocia una señal de salida a cada
transición
• Moore: asocia una señal de salida a cada
estado
De Moore a Mealy
• Sea M1 un autómata de Moore y M2 un
autómata de Mealy, con cada transición, M2
emite la misma salida que M1 asocia con el
estado ingresado.
MO
0
1
ME
0
1
0
1
q0/a
q0
q1
q0
q0
q1
a
b
q1/b
q2
q0
q1
q2
q0
a
a
q2/a
q1
q0
q2
q1
q0
b
a
Ejemplo
MO
0
1
ME
0
1
0
1
q0/0
q8
q1
q0
q8
q1
1
1
q1/1
q8
q2
q1
q8
q2
1
1
q2/1
q3
q2
q2
q3
q2
0
1
q3/0
q4
q2
q3
q4
q2
0
1
q4/0
q4
q5
q4
q4
q5
0
1
q5/1
q4
q5
q5
q4
q5
0
1
q6/0
q7
q5
q6
q7
q5
0
1
q7/0
q6
q7
q7
q6
q7
0
0
q8/1
q7
q1
q8
q7
q1
0
1
Minimización de autómata de Mealy
• Agrupar estados con salidas idénticas.
– P(1) = {q0, q1}, {q7}, {q2, q3, q4, q5, q6, q8}
• Analizar cada clase de equivalencia.
– Analizar la clase con más estados:
•
{q2, q3, q4, q5, q6, q8}
Análisis de {q2, q3, q4, q5, q6, q8}
• Debemos comprobar que todas las
combinaciones posibles dentro de esta clase se
relacionen en un mismo nivel, es decir:
–
–
–
–
–
q2 En q3
q2 En q4
q2 En q5
q2 En q6
q2 En q8
• Para n = 1, 2, 3, 4…
• Pero ya sabemos que q2 E1 q3,4,5,6,8 dado
que pertenecen a la misma clase de
equivalencia, por lo tanto sólo nos queda
comprobar que las salidas para cada transición
sean iguales. Por ejemplo:
a
(q2, a)
FS(q2, a)
(q3, a)
FS(q3, q)
0
q3
01
q4
01
1
q2
01
q2
01
Siguiendo con el análisis…
a
(q2, a)
FS(q2, a)
(q4, a)
FS(q4, q)
0
q3
01
q4
01
1
q2
01
q5
01
a
(q2, a)
FS(q2, a)
(q5, a)
FS(q5, q)
0
q3
01
q4
01
1
q2
01
q5
01
a
(q2, a)
FS(q2, a)
(q6, a)
FS(q6, q)
0
q3
01
q7
01
1
q2
01
q5
01
a
(q2, a)
FS(q2, a)
(q8, a)
FS(q8, q)
0
q3
01
q7
01
1
q2
01
q1
01
Análisis de la clase {q0, q1}
• Comprobemos que las salidas para las
transiciones de q0 y q1 son iguales:
a
(q0, a)
FS(q0, a)
(q1, a)
FS(q1, a)
0
q8
01
q8
01
1
q1
11
q2
01
• Por lo tanto esta clase se divide en dos: {q0}, {q1}
Finalmente?
• Ahora tenemos las siguientes particiones:
– P(1) = {q0, q1}, {q7}, {q2, q3, q4, q5, q6,q8}
– P(2)= {q0}, {q1}, {q7}, {q2, q3, q4, q5, q6,q8}
• Como no son iguales debemos continuar…
– Analizar la clase {q2, q3, q4, q5, q6, q8}
Análisis de la clase {q2, q3, q4, q5, q6, q8}
• Verificar q2 E3 q3,4,5,6,8
ab
(q2, ab)
FS(q2, ab)
(q3, ab)
FS(q3, ab)
00
q4
01
q4
01
01
q2
01
q5
01
11
q2
01
q2
01
10
q3
01
q3
01
• Y así sucesivamente hasta encontrar P(3),
P(4)…
Ahora si!
• Tenemos que las particiones son:
– P(1) = {q0, q1}, {q7}, {q2, q3, q4, q5, q6,q8}
– P(2)= {q0}, {q1}, {q7}, {q2, q3, q4, q5, q6,q8}
– P(3)= {q0}, {q1}, {q7}, {q6, q8}, {q2, q3, q4, q5}
– P(4) = {q0}, {q1}, {q7}, {q6}, {q8}, {q2, q3, q4, q5}
– P(5) = {q0}, {q1}, {q7}, {q6}, {q8}, {q2, q3, q4, q5}
• P(4) = P(5)!!!
Nuestro autómata minimal
Descargar

Minimización Autómata de Moore