5. Zostavenie maximálnych tried zlučiteľnosti

Pri hľadaní úplného prípustného súboru tried zlučiteľnosti je vhodné nájsť najskôr zoznam všetkých maximálnych tried zlučiteľnosti. Túto úlohu je možné riešiť nasledujúcou procedúrou, ktorá vychádza z vyriešenej implikačnej tabuľky
.
Procedúra (Zostavenie maximálnych tried zlučiteľnosti)

  1. Najskôr sa vytvorí zoznam tried zlučiteľnosti (zoznam C) vypísaním všetkých zlúčiteľných dvojíc implikačnej tabuľky pri prvom stĺpci sprava, v ktorom je aspoň jedno nepreškrtnuté políčko.
  2. Stĺpce implikačnej tabuľky sa postupne preberú sprava doľava takto: Nech Si je množina obsahujúca všetky tie stavy, ktorým v i-tom stĺpci zodpovedá nepreškrtnuté políčko. Urobí sa prienik množiny Si s každou triedou Cj v doteraz vytvorenom zozname C. Ak je niektorý prienik neprázdny, k zoznamu C sa pridá nová trieda {{i} + { SiÇSj}}. Z nového zoznamu C sa odstránia všetky duplicity a všetky triedy obsiahnuté v iných. Potom sa do zoznamu pridajú všetky dvojice zlúčiteľných stavov, vytvorené zo stavu i a každého takého stavu v Si, ktorý nie je ani v jednom prieniku.
  3. Konečný zoznam zväčšený o všetky jednoprvkové triedy zlučiteľnosti stavov, ktoré nie sú obsiahnuté ani v jednej triede zoznamu C, predstavuje všetky maximálne triedy zlučiteľnosti daného automatu.
(viď príklad)