Fsm

Page 1

A partire dalla prima macchina, con stati S0 e S1 (e S0 di reset), costruiamo una macchina con stati ridondanti: la macchina finale, con stati A,B,C,D,E,F ha due partizioni per costruzione. {A,E,F } e {B,C,D}. Sapendo che questo è il risultato, svolgiamo l’esercizio: Data la seguente macchina, identificarne quella minima. 0 1 Out A C D 0 B F E 1 C E F 1 D A E 1 E D C 0 F B D 0 Raggiungibilità A  A{C,D} ; A{C,D}  A{C{E,F},D{A,E}}  A{C{E,F},D{}}; A{C{E{D,C},F{B,D}},D{}}  A{C{E{}},F{B}},D{}} ; A{C{E{}},F{B}},D{}}  A{C{E{}},F{B{E,F}}},D{}}  A{C{E{}},F{B{}}},D{}} FINE. Tutti Raggiungibili S0/0 S1/1 0,1 0,1 0 S0/0 S1/1 S1’/1 S0’/0 S0”/0 S1”/1 1 0 1 0 0 1 0 1 0 1 1 0 A/0 D/1 C/1 E/0 F/0 B/1 1 0 1 0 1 0 1 0 1 1 0 B X C X EF D X AE AE, EF E CD X X X F BC X X X BD, CD A B C D E Analisi stati distinguibili: Nessuna distinguibilità retropropogabile. Tutte le coppie di stati sono equivalenti Grafo delle equivalenze Due classi di equivalenza. MODIFICA 1 FSM Modifichiamo la macchina di partenza inserendo delle condizioni di indifferenza. Lo scopo è costruire un esercizio differente sapendo già che avremo almeno due classi di massima compatibilità che corrispondono alla realizzazione minima. 0 1 Out A C D 0 B F E - C E F 1 D A E 1 E D C - F B D 0 A B C F E D B CF, DE C X EF D X AE AE, EF E CD DF, CE DE, CF AD, CE F BC DE X X BD, CD A B C D E Analisi stati distinguibili: B X C X EF D X AE AE, EF E CD X X X F BC DE X X BD, CD A B C D E Passo 2 B X C X EF D X AE AE, EF E CD X X X F BC X X X BD, CD A B C D E Passo 3 B X C X EF D X AE AE, EF E CD X X X F BC X X X BD, CD A B C D E Nessuna ulteriore distinguibilità retropropogabile. Tutte le coppie rimaste si riferiscono a stati equivalenti 2 classi di massima compatibilità, che hanno i seguenti Vincoli riclassificati: A B C F E D CD…