1.5. Abstraktná syntéza

Tento algoritmus popisuje syntézu automatu M = ( X, S, Y, , ), s množinou výstupov Y = {0, I}, ktorý rozpoznáva udalosť E vzhľadom na výstup I. Algoritmus vyzerá následovne:

  1. Pre danú regulárnu udalosť E sa nájdu všetky rôzne derivácie udalosti E podľa všetkých slov eX*, t.j. zostaví sa množina D

    Pretože E je regulárna udalosť, množina D má konečný počet prvkov.

  2. Ku každej derivácii z D sa priradí jeden stav automatu M. Derivácii E/ = E sa priradí počiatočný stav S0.

  3. Zostaví sa množina K koncových stavov automatu M:

    Množinu K tvoria všetky stavy automatu, ktoré boli priradené deriváciám z D, ktoré obsahujú v sebe prázdne slovo X*. Množina K obsahuje práve tie stavy automatu M, do ktorých sa môže automat dostať z počiatočného stavu, ak príjme vstupné slovo z udalosti E. Toto tvrdenie vyplýva z bodu 2 a z definície derivácie.

  4. Určí sa prechodová funkcia automatu M:

    Ak , pričom e, wX*, x X a derivácie a sú priradené stavom S a S' tak (S, x) = S'.

  5. Výstupná funkcia sa zostaví takto:

    pri automate typu Moore:

    (S) = I SK, t.j. S je koncový stav,

    pri automate typu Mealy:

    (S, X) = I (S, X)K.