viernes, 11 de diciembre de 2009

MINIMIZACIÓN

Si queremos calcular el autómata mínimo equivalente de cierto autómata, tenemos que obtener el conjunto cociente Q/E.

Para ello, asignamos clases a los diferentes estados, siendo para la primera iteración, C1( clase 1 ) para los estados finales y C2( clase 2 ) para el resto de estados.
Q/E0={ C1(p, q, r) , C2(s, t, u, v)}




Posteriormente analizando la nueva tabla de transiciones, comprobamos si se ha creado alguna clase nueva, que denominaremos como C3. En este caso el estado “s” es distinto al resto de estados de la clase 2, por lo tanto se le asignará C3 a dicho estado, pasando a ser Q/E1 = {C1(p, q, r), C2( s), C3(t, u, v)}

Q/E1
abab
*ppqC1C1
*qrpC1C1
*rrrC1C1
->stpC2C1
ttuC2C2
utvC2C2
vvuC2C2





A continuación, hemos comprobado que no se ha creado ninguna clase extra, por lo tanto, el Q/E2 será el mínimo equivalente. Para representar dicho autómata, consideraremos las clases como los estados y representaremos sus correspondientes transiciones.

Q/E2
ab
*pC1C1
*qC1C1
*rC1C1
->sC3C1
tC3C3
uC3C3
vC3C3




1 comentario: