minimizacion_automatas
DESCRIPTION
automatasTRANSCRIPT
![Page 1: MINIMIZACION_AUTOMATAS](https://reader031.vdocumento.com/reader031/viewer/2022020417/563db7cf550346aa9a8e2cb5/html5/thumbnails/1.jpg)
MINIMIZACIÓN DE AUTÓMATAS
![Page 2: MINIMIZACION_AUTOMATAS](https://reader031.vdocumento.com/reader031/viewer/2022020417/563db7cf550346aa9a8e2cb5/html5/thumbnails/2.jpg)
AUTÓMATA FINITO DETERMINISTA
El término «determinista» hace referencia al hecho de
que para cada entrada sólo existe uno y sólo un estado
al que el autómata puede hacer la transición a partir de
su estado actual
Cada estado cumple
una sola condición
que solo puede estar
en un único estado
después de leer
cualquier secuencia
de entradas
Salen de este
estado un cero y un
uno, lo cual significa
que va por 0 o va
por 1
![Page 3: MINIMIZACION_AUTOMATAS](https://reader031.vdocumento.com/reader031/viewer/2022020417/563db7cf550346aa9a8e2cb5/html5/thumbnails/3.jpg)
5-tupla (K, Σ, δ, s, F)
donde:
M = { q0, q1, q2 , q3, q4 , q5, q6 , q7} , {0, 1} , δ, q0, {q2})
K ={q0, q1, q2 , q3, q4 , q5, q6 , q7} (Estados)
Σ {0, 1} (Alfabeto)
s = q0 (Estado Inicial)
F = q2 (Estado Final)
QUINTUPLA
Estado final
Estado Inicial
Alfabeto
![Page 4: MINIMIZACION_AUTOMATAS](https://reader031.vdocumento.com/reader031/viewer/2022020417/563db7cf550346aa9a8e2cb5/html5/thumbnails/4.jpg)
Donde la función δ : { q0, q1, q2 , q3, q4 , q5, q6 , q7} × {0,
1} → { q0, q1, q2 , q3, q4 , q5, q6 , q7} viene dada por:
TRANSICIONES
δ(q0, 0) = q1
δ(q0, 1) = q5
δ(q1, 0) = q6
δ(q1, 1) = q2
δ(q2, 0) = q0
δ(q2, 1) = q2
δ(q3, 0) = q2
δ(q3, 1) = q6
δ(q4, 0) = q7
δ(q4, 1) = q5
δ(q5, 0) = q2
δ(q5, 1) = q6
δ(q6, 0) = q6
δ(q6, 1) = q4
δ(q7, 0) = q6
δ(q7, 1) = q2
![Page 5: MINIMIZACION_AUTOMATAS](https://reader031.vdocumento.com/reader031/viewer/2022020417/563db7cf550346aa9a8e2cb5/html5/thumbnails/5.jpg)
Conjuntos
CONJUNTOS
X = {q2}
Aceptadores
No
Aceptadores
Y = {q0, q1, q3, q4, q5, q6 q7}
![Page 6: MINIMIZACION_AUTOMATAS](https://reader031.vdocumento.com/reader031/viewer/2022020417/563db7cf550346aa9a8e2cb5/html5/thumbnails/6.jpg)
Validando información del conjunto X
MINIMIZACIÓN AFD
X = {q2}
0 1
q2 Y X
Y = {q0, q1, q3, q4, q5, q6 q7}
Valida
valores de q2
Valida q2 en
la transición
0 = q0
q0 se
encuentra en
el conjunto Y
∑ = {0,1}
El mismo proceso se realiza con el
estado q2 con la transición 1, entonces:
q2,1=q2 y q2 se encuentra en el
conjunto X
![Page 7: MINIMIZACION_AUTOMATAS](https://reader031.vdocumento.com/reader031/viewer/2022020417/563db7cf550346aa9a8e2cb5/html5/thumbnails/7.jpg)
MINIMIZACIÓN AFD
0 1
q0 Y Y
q1 Y X
q3 X Y
q4 Y Y
q5 X Y
q6 Y Y
q7 Y X
Validando información del conjunto Y
X = {q2}
Y = {q0, q1, q3, q4, q5, q6 q7}
q0, q4, q6
Son
équivalentes
q1, q7
Son
équivalentes
q3, q5
Son
équivalentesSe generan 3
conjuntos
![Page 8: MINIMIZACION_AUTOMATAS](https://reader031.vdocumento.com/reader031/viewer/2022020417/563db7cf550346aa9a8e2cb5/html5/thumbnails/8.jpg)
MINIMIZACIÓN AFD
0 1
q0 Z N
q4 Z N
q6 M M
Generando Nuevos Conjuntos
X = {q2}
M = {q0, q4, q6}
q0, q4
Son
équivalentesq6, NO
es
équivalenteSe generan 2
conjuntos
Z = {q1, q7}
N = {q3, q5}
Validando conjunto M
![Page 9: MINIMIZACION_AUTOMATAS](https://reader031.vdocumento.com/reader031/viewer/2022020417/563db7cf550346aa9a8e2cb5/html5/thumbnails/9.jpg)
MINIMIZACIÓN AFD
0 1
q1 M X
q7 M X
Validando Conjuntos
X = {q2}
M = {q0, q4, q6}
q1, q7
Son
équivalentes
Z = {q1, q7}
N = {q3, q5}
Validando conjunto Z
![Page 10: MINIMIZACION_AUTOMATAS](https://reader031.vdocumento.com/reader031/viewer/2022020417/563db7cf550346aa9a8e2cb5/html5/thumbnails/10.jpg)
MINIMIZACIÓN AFD
0 1
q3 X M
q5 X M
Validando Conjuntos
X = {q2}
M = {q0, q4, q6}
q3, q5
Son
équivalentes
Z = {q1, q7}
N = {q3, q5}
Validando conjunto N
![Page 11: MINIMIZACION_AUTOMATAS](https://reader031.vdocumento.com/reader031/viewer/2022020417/563db7cf550346aa9a8e2cb5/html5/thumbnails/11.jpg)
MINIMIZACIÓN AFDEN CONCLUSIÓN AL VALIDAR LOS CONJUNTOS
0 1
q3 X M
q5 X M
X = {q2}
M = {q0, q4, q6}
q3, q5
Son
équivalentes
Z = {q1, q7}
N = {q3, q5}
Validando conjunto N
0 1
q2 M X
Validando conjunto X
0 1
q0 Z N
q4 Z N
q6 M M
q0, q4
Son
équivalentesq6, NO
es
équivalente
Validando conjunto M
0 1
q1 M X
q7 M Xq1, q7
Son
équivalentes
Validando conjunto Z
Se generan
dos conjuntos
![Page 12: MINIMIZACION_AUTOMATAS](https://reader031.vdocumento.com/reader031/viewer/2022020417/563db7cf550346aa9a8e2cb5/html5/thumbnails/12.jpg)
MINIMIZACIÓN AFDDESAPARECE M Y SE CREAN DOS CONJUNTOS
0 1
q3 X B
q5 X B
X = {q2}
A = {q0, q4}
q3, q5
Son
équivalentes
Z = {q1, q7}
N = {q3, q5}
Validando conjunto N
0 1
q2 A X
Validando conjunto X
0 1
q0 Z N
q4 Z N
q0, q4
Son
équivalentes
Validando conjunto A
0 1
q1 B X
q7 B Xq1, q7
Son
équivalentes
Validando conjunto Z
B = {q6}
Generando Nuevos Conjuntos
0 1
q6 B A
Validando conjunto B
Nota: Al generar nuevos conjuntos se
vuelve a validar todos los conjuntos
![Page 13: MINIMIZACION_AUTOMATAS](https://reader031.vdocumento.com/reader031/viewer/2022020417/563db7cf550346aa9a8e2cb5/html5/thumbnails/13.jpg)
AUTÓMATA MINIMIZADO
0 1
A Z N
X A X
B B A
Z B X
N X B
Creando nueva tabla de transición
A
Z
# 0
N
1
X
0
1
B
0
1
0
1
0
1
Graficando el autómata