3. Zostavenie automatu pokrývajúceho zadaný automat

Nech T = {C1, ...,Cm} je súbor tried zlučiteľnosti na množine stavov automatu M' = (X, S', Y, d', l'). Automat M = (X, S, Y, d, l), ktorý pokrýva automat M', sa zostaví nasledovne. Každej triede súboru T sa priradí jeden stav automatu M, t. j. S = {s1, ..., sm}. Prechodová funkcia d sa zostaví tak, že pre každý vstup x Î X platí:

{d' (s', x) | s'ÎCi}Í Cj Ţ  d (si, x)= sj


Ak nasledujúce stavy d'(s', x) nie sú definované pre žiadny stav s' Î Ci, tak ani d (si, x) nie je definované. Výstupná funkcia sa zostaví nasledovne: 
- pre automat typu Mealy l(si, x) = l'(s', x)
- pre automat typu Moore l(si) = l'(s'),
kde s' je ľubovoľný stav z Ci, v ktorom je definovaná funkcia l'. Ak funkcia l'(s', x) nie je definovaná pre žiadny stav s'ÎCi, potom nie je definovaná ani l(si, x) alebo l(si). (viď príklad)

Zostavenie minimálneho súboru je ťažká úloha. Množina všetkých maximálnych tried zlučiteľnosti je síce prípustná a možno ju urobiť aj úplnou, avšak vo všeobecnosti nie je minimálna. Opak sa objavuje iba v niektorých prípadoch, napr. pri úplne určených automatoch.
Ešte pred procesom hľadania minimálneho súboru tried zlučiteľnosti sa však treba zaoberať problémom zostavenia dvojíc zlučiteľných stavov a maximálnych tried.