El enunciado aquí Practica 6 Talf
1.-Minimiza el autómata A1 = ({0,1},{q0, q1, q2, q3, q4}, f, q0,{q1, q2}) en donde f se define como:
- f(q0, 0) = q3
- f(q0, 1) = q2
- f(q1, 0) = q4
- f(q1, 1) = q1
- f(q2, 0) = q0
- f(q2, 1) = q3
- f(q3, 0) = q0
- f(q3, 1) = q2
- f(q4, 0) = q4
- f(q4, 1) = q1
modelamos el autómata en JFlap
para minimizarlo vamos al menu “Convert”->”minimize DFA”
obviamente los estados q1 y q4 quedan fuera porque no están asociados al grafo del estado inicial.
Pinchamos en el botón “Finish”
pinchamos en “complete” y en “done?” por lo que se mostrara el autómata minimizado en una nueva ventana
2. Indica cuáles de los siguientes autómatas son equivalentes entre sí:
- AF1={{a,b},{p,q,r,s,t,u}, f1, p, {q,r}}
- AF2={{a,b},{p,q,r,s,t,u}, f2, p, {u}}
- AF3={{a,b},{p,q,r,s,t,u}, f3, p, {s,t,u}}
- AF4={{a,b},{p,q,r,s,t,u}, f4, p, {r,s}}
- AF5={{a,b},{p,q,r,s,t}, f5, p, {r,s}}
Autómata 1
| F1 | a | b |
| p | q | p |
| q | r | s |
| r | q | t |
| s | t | u |
| t | s | u |
| u | q | u |
modelamos el autómata en JFlap
autómata 2
| F2 | a | b |
| p | q | u |
| q | r | t |
| r | s | t |
| s | r | t |
| t | u | s |
| u | u | q |
modelamos el autómata en JFlap
autómata 3
| F3 | a | b |
| p | u | q |
| q | t | r |
| r | s | r |
| s | t | r |
| t | u | q |
| u | s | p |
modelamos el autómata en JFlap
autómata 4
| F4 | a | b |
| p | r | q |
| q | r | q |
| r | s | t |
| s | r | t |
| t | t | q |
| u | u | p |
modelamos el autómata en JFlap
autómata 5
| F5 | a | b |
| p | q | r |
| q | q | t |
| r | s | q |
| s | r | q |
| t | r | q |
modelamos el autómata en JFlap
En la ventana de JFlap donde esta contenido el aútomata pintamos en “Test -> Compare Equivalence” y nos dice si es equivalente o no.
de la comprobación sacamos la siguiente tabla
| @ | AF1 | AF2 | AF3 | AF4 | AF5 |
| AF1 | – | F | F | V | F |
| AF2 | – | – | F | F | V |
| AF3 | – | – | – | F | F |
| AF4 | – | – | – | – | F |
| AF5 | – | – | – | – | – |
Por lo tanto los autómatas equivalentes son AF1 con AF4 y AF2 con AF5