Minimización de estados. Modo Reloj.

Minimización de estados. Modo Reloj.

de Andres Guido Acerenza -
Número de respuestas: 2

Hola, 
tengo la siguientes dudas: 

Si estoy minimizando una tabla de estados y el método de minimización de "la escalera" me queda como la imagen que adjunto, entonces, ¿como debo agrupar los estados equivalentes? 
Yo los agrupé como muestro en el recuadro ( qA=(q5,q6), qB=(q0,q3), qC=(q1,q4), qD=(q2) ). (no se si es correcto)
Y luego hice la "nueva" tabla con  estos nuevos estados. Mi problema surge cuando quiero asignar los próximos estados en la tabla nueva, ya que encuentro incompatibilidades. Por ejemplo: cuando estoy en el estado qC y me llega una entrada 00, ¿que estado le asigno como próximo estado?, ¿qA=(q5,q6) o qB=(q0,q3)?. Adjunto la tabla de estados "vieja" (sin minimizar) y la "nueva".
En pocas palabras me gustaría saber si existe algún método para agrupar estos estados. Estuve revisando las clases y no encontré esa información.
Saludos,
Andrés.


Adjunto 10.jpg
En respuesta a Andres Guido Acerenza

Re: Minimización de estados. Modo Reloj.

de Leandro Diaz -
Hola, la manera de agrupar está mal. Tú agrupaste (1,4) como estado compatible pero si te fijas bien, (1,4) es compatible si lo es (0,6). Si quieres que (1,4) sea compatible debes elegir si o si (0,6) también.

Te conviene realizar el grafo, poniendo en los nodos las parejas candidatas a ser compatibles y si hay una pareja que necesita que otra pareja sea compatible, lo indicas con una flecha. ( En este caso una pareja candidata a compatible sería (1,4) y tendría una flecha hacia (0,6), ya que para que (1,4) sea compatible se debe cumplir (0,6) )

Luego que haces el grafo debes encontrar la zona mínima en la cual estén todos los estados originales y no tenga flechas salientes. ( Si haces esto, verás que te queda una flecha saliente de (1,4) apuntando a (0,6) y te darás cuenta de que tu elección está mal)

Capaz te queda más claro mirando https://open.fing.edu.uy/courses/dl/14, a partir del minuto 29:38 lo explica y hace un ejemplo más corto, y luego aplicas lo mismo para este ejemplo.