4. Zostavenie množiny všetkých zlučiteľných dvojíc

Dva stavy s a s' automatu M = (X, S, Y, d, l) sú zlúčiteľné vtedy a len vtedy, ak pre každý vstup x Î X platí:
1. l (si, x) = l'(s', x) pre automat typu Mealy a l (si) = l'(s') pre automat typu Moore vždy vtedy, ak sú definované obidva výstupy.
2. d (s, x) = d (s', x) v prípade, že obidva stavy sú definované.
Na základe tejto vety možno formulovať procedúru, ktorej výsledkom sú všetky zlúčiteľné alebo nezlúčiteľné dvojice stavov daného automatu M. 

Procedúra (Zostavenie dvojíc zlučiteľných stavov.)

  1. Označia sa tie dvojice s, s', pre ktoré l (s, x) ą l (s', x) pre niektorý vstup x. Tieto dvojice sú nezlúčiteľné.
  2. Ak pre niektorú dvojicu s, s' platí l (s, x) = l (s', x) pri všetkých vstupoch x, pri ktorých sú definované obidva výstupy, tak pre túto dvojicu sa vypíšu všetky dvojice stavov s1, s1', ktoré dvojica s, s' implikuje.
  3. Pri všetkých dvojiciach s, s', ktoré neboli doteraz označené ako nezlúčiteľné, sa preskúmajú nimi implikované dvojice.
  4. Ak niektorá dvojica s, s' implikuje nezlúčiteľnú dvojicu, tak sa označí ako nezlúčiteľná a prejde sa na krok 3. Ak žiadna takáto dvojica neexistuje, procedúra končí. Všetky neoznačené dvojice sú zlúčiteľné.

Pri riešení procedúry možno použiť implikačnú tabuľku. Implikačná tabuľka predstavuje polovičnú maticu, v ktorej každej dvojici stavov je priradené jedno políčko. Keďže zlučiteľnosť je symetrická netreba registrovať obidve kombinácie stavov s, s', preto je tabuľka polovičná.
Do políčok implikačnej tabuľky, zodpovedajúcim jednotlivým dvojiciam stavov s, s' automatu, sa zapisujú dvojice implikovaných stavov. Ak dvojica neimplikuje žiadnu inú dvojicu, potom príslušné políčko ostáva prázdne. Nezlučiteľnosť dvojice sa označí preškrtnutím príslušného políčka. Všetky políčka, ktoré na konci procedúry ostanú nepreškrtnuté, zodpovedajú zlúčiteľným dvojiciam stavov. (viď príklad)