Pokial automat minimalizujeme, tak sa nemoze stat, ze jeho "minimalna verzia" sa sprava odlisne. Preto tieto automaty musia byt ekvivalentne. Dva automaty su ekvivalentne vtedy, ak pre kazdu postupnost vstupnych symbolov existuje rovnaka postupnost vystupnych symbolov. Ekvivalentne nemusia byt len automaty ako celok, ale mozu byt aj stavy. Stavy su ekvivalentne, ak pre vsetky ich vstupne symboly maju rovnaky vystupny symbol a ekvivalentne nasledne stavy.
Ekvivalencia vnutornych stavov moze byt
- prosta ekvivalencia
Dva vnutorne stavy maju zhodne vsetky nasledne vnutorne stavy aj vystupne symboly
- psedoekvivalencia
Vyskytuje sa v neuplne urcenych automatch (?). Dva stavy su pseudoekvivalentne, ak ich urcene vnutorne stavy a vystupne symboly su ekvivalentne
- k-ekvivalencia
Dva stavy su k-ekvivalentne ak pre dany vst. symbol sa z oboch stavov po k prechodoch dostaneme do rovnakeho stavu, alebo do dvoch ekvivalentnych stavov. Oba stavy musia mat rovnake vyst. symboly.
Pseudoekvivalenciu nechame zit vlastnym zivotom a budeme sa venovat k- a prostej ekvivalencii.
Postup pri minimializacii
Minimalizovat mozme pomocou implikacnej tabulky, alebo pomocou "zgrupovania" stavov v tabulke prechodov. A implikacna tabulka je trosku prehladnejsia a tazsie sa v nej pomylit:), tak ja sa budem drzat jej. Vysledkom je samozrejme rovanky pri oboch postupoch.
Implikacna tabulka
pracovat budeme s tymto automatom
0 1 | 0 1
Q1 Q4 Q5 0 0
Q2 Q8 Q3 0 0
Q3 Q4 Q2 1 0
Q4 Q1 Q8 1 0
Q5 Q8 Q2 1 0
Q6 Q4 Q1 1 0
Q7 Q4 Q6 0 0
Q8 Q2 Q4 1 0
1. z prechodovej tabulky nacrtneme kostru impl. tabulky
2
3
4
5
6
7
8
1 2 3 4 5 6 7
2. preskrtne tie bunky, kde Qi a Qj maju rozne vystupy, pretoze tie stavy nebudu ekv. z deifinicie
2
3 X X
4 X X
5 X X
6 X X
7 X X X X
8 X X X
1 2 3 4 5 6 7
3. do kazdej nepreskrtnutej bunky opiseme dvojice novych stavov pre vsetky hodnoty vstupov
2 4,8
3,5
3 X X
4 X X 4,1
2,8
5 X X 4,8 1,8
2.2 8,2
6 X X 4,4 1,4 8,4
2,1 8,1 2,1
7 4,4 4,8 X X X X
5,6 3,6
8 X X 4,2 1,2 8,2 4,2 X
2,4 8,4 2,4 1,4
1 2 3 4 5 6 7
4. teraz musim skontrolovat jednotlive stavy a moznosti zlucitelnosti stavov z tabulky
Napr. ak maju byt ekv. stavy 2 a 1, tak musia byt ekv. stavy 4,8 a 3,5
2-1: OK
4-3: NOK, 1-4 nejde ...
5-3: OK
5-4: NOK
6-3: OK
6-4: NOK
6-5: OK
7-1: OK
7-2: OK
8-3: NOK
8-4: OK
8-5: NOK
8-6: NOK
Vysledkom je, ze mozme zlucit stavy:
7 s 1 a 2 - zaradime do "kategorie" A
3 s 5 a 6 - zaradime do "kategorie" B
5 so 6 - zaradime do "kategorie" B, pretoze sa jedna o rovnaky vystup
4 s 8 - zaradime do "kategorie" C
5. Dostaneme novu tabulku, z ktorej uz lahko zostrojime automat
0 1 | 0 1
A C B 0 0
B C A 1 0
C A C 1 0
