Practica 6 Talf

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

modelado automata ejercicio 1para minimizarlo vamos al menu “Convert”->”minimize DFA”

minimizando paso 1obviamente los estados q1 y q4 quedan fuera porque no están asociados al grafo del estado inicial.

Pinchamos en el botón “Finish”

minimizado paso 2pinchamos en “complete” y en “done?” por lo que se mostrara el autómata minimizado en una nueva ventana

afd minimo

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

automata 1

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

automata 2

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

automata 3

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

automata 4

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

automata 5

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