7. Zostavenie množiny všetkých prostých tried

Proces zostavenia množiny prostých tried zlučiteľnosti daného automatu vychádza z maximálnych tried, ktoré sú samy o sebe prosté. Zvyšné prosté triedy je možné získať v procese postupného štiepenia tried na podtriedy pri súčasnom porovnávaní implikovaných množín. Tento problém je možné riešiť pomocou nasledujúcej procedúry:

Procedúra (zostavenie zoznamu všetkých prostých tried zlučiteľnosti)

  1. Vytvorí sa začiatok zoznamu prostých tried vypísaním všetkých maximálnych tried v poradí podľa klesajúceho počtu prvkov v triedach. Označia sa (podčiarknutím) tie maximálne triedy, ktoré implikujú prázdne množiny.
  2. Zo zoznamu P sa vyberie nasledujúca neprečiarknutá a nepodčiarknutá trieda. Ak sa prešiel celý zoznam P, tak sa prejde na krok 5, inak sa prejde na krok 3 (na začiatku procedúry sa vychádza z prvej nepodčiarknutej maximálnej triedy v zozname).
  3. Z vybratej triedy sa zostavia jej podtriedy so zmenšeným počtom prvkov o jednotku. Podtriedy, ktoré sa zatiaľ v zozname P nevyskytujú (vrátane prečiarknutých), sa pripíšu na koniec zoznamu. Pripísané podtriedy, ktoré implikujú prázdne množiny, sa podčiarknu. Prejde sa na krok 4.
  4. Pripísané podtriedy sa porovnajú jednotlivo so všetkými triedami zoznamu P, ktoré ich obsahujú. Triedy vylúčené inými triedami sa označia (prečiarknutím). (Ak je pripísaná trieda podtriedou niektorej podčiarknutej triedy, tak ju možno automaticky prečiarknuť). Prejde sa na krok 2.
  5. Procedúra sa končí. Neprečiarknuté triedy zoznamu P sú všetky prosté triedy zlučiteľnosti.