1. Pokrytie a ekvivalencia automatov

Nech M = (X, S, Y, d, l) a M' = (X, S', Y, d', l') sú dva neúplné automaty. Stav s Î S pokrýva stav s' Î S' ( s ł s') vtedy a len vtedy, ak pre každé prípustné slovo e a pre M a M' zo stavu s a s' platí:
l (s, e) = l'( s', e)

práve vtedy, ak výstupná funkcia automatu M', t.j. funkcia l', je definovaná. (viď príklad)

Automat M pokrýva automat M' ( M ł M') vtedy a len vtedy, ak pre každý stav s' automatu M' existuje taký stav s automatu M, že s ł s'.
Ak automat M pokrýva automat M', tak predstavuje dokonalú náhradu automatu M'. V definovaných bodoch sa správa M rovnako ako M', t.j. pre to isté vstupné slovo dáva ten istý výstup. Každý sekvenčný obvod, ktorý zodpovedá automatu M, zodpovedá aj automatu M'. Relácia pokrytia je reflexívna (t.j. každý automat pokrýva sám seba) a tranzitívna (t.j. ak M ł M' a súčasne M' ł M'', tak M ł M''), ale nie je symetrická ( t.j. z M ł M' nevyplýva M' ł M ) . 
Dva automaty M a M' sa nazývajú ekvivalentné ( M ş M' ) vtedy a len vtedy, ak platí M ł M' a súčasne M' ł M. V prípade ekvivalencie sú obidva automaty vzájomne nahraditeľné. 
Pri syntéze automatu je potrebné riešiť nasledujúci problém. Pri zadanom automate M sa hľadá ekvivalentný automat M' s minimálnym počtom stavov. Takýto automat sa nazýva minimálny alebo redukovaný. Pre úplný automat existuje jediný minimálny automat (ekvivalentný s daným automatom).