2. Zlučiteľnosť stavov a triedy zlučiteľnosti

Dva stavy s a s' automatu M = (X, S, Y, d, l) sa nazývajú zlúčiteľné ( s = s' ) vtedy a len vtedy, ak pre každé vstupné slovo e, prípustné pre M platí:

l (s, e) = l (s', e)

v prípade, že obidva výstupy sú definované.(príklad Zlučiteľnosť 1)
Z definície zlučiteľnosti vyplýva, že táto relácia je reflexívna a symetrická, avšak nie je tranzitívna ( z toho, že s=s' a s' = s'' nevyplýva, že s = s'').(príklad Zlučiteľnosť 2)

    V prípade úplného automatu je relácia zlučiteľnosti aj tranzitívna a teda je ekvivalenciou, preto sa stavy, ktoré sú zlúčiteľné nazývajú ekvivalentné.
V množine stavov daného automatu možno nájsť triedy, ktoré obsahujú iba vzájomne zlúčiteľné stavy. Tieto triedy sa nazývajú triedy zlúčiteľných stavov alebo triedy zlučiteľnosti. Maximálna trieda zlučiteľnosti je taká trieda zlučiteľnosti Ci, pre ktorú neexistuje žiadna iná trieda zlučiteľnosti Cj , taká že Ci Í Cj.

    Nech M = (X, S, Y, d, l) a M' = (X, S', Y, d', l') sú dva neúplné automaty. Ak stav s Î S pokrýva niektorú množinu stavov C Í S', potom C je trieda zlučiteľnosti.

    Nech T = {C1,. . .,Cm} je súbor, v ktorom Ci sú triedy zlučiteľnosti, v množine stavov niektorého automatu M' = (X, S', Y, d', l'). Súbor T sa nazýva prípustný vtedy a len vtedy, ak pre každú triedu Ci ={si1, si2, ..., sik} a pre každý vstup x ÎX množina stavov {d (si1, x), ..., d (sik,x)} padne do niektorej triedy Cj Î T. Súbor T sa nazýva úplný vtedy a len vtedy, ak každý stav automatu M' je obsiahnutý aspoň v jednej triede z T.

    Nech T = {C1, ..., Cm} je úplný súbor tried zlučiteľnosti v množine S' automatu M' = (X, S', Y, d', l'). Nech M = (X, S, Y, d, l) je automat s množinou stavov S = {s1,...,sm}. Automat M pokrýva M' tak, že každý stav si ÎS pokrýva práve jednu triedu Ci Î T vtedy a len vtedy, ak súbor T je prípustný. Z tejto vety vyplýva spôsob zostavenia automatu M, ktorý pokrýva automat M' a má menší alebo minimálny počet stavov. Ak sa podarí v množine stavov automatu M' zostaviť prípustný a úplný súbor tried zlučiteľnosti, ktorý obsahuje menší počet tried ako je počet stavov, alebo obsahuje minimálny možný počet tried, potom možno zostaviť automat M, ktorý pokrýva automat M' a pritom má menší alebo minimálny počet stavov.