| Abstrakt: | Nedeterminizmus do konečných automatov zaviedli Rabin a Scott, čím získali zariadenie s rovnakou výpočtovou silou, ktoré je možné jednoduchšie zapísať. Neskôr sa nedeterminizmus začal považovať za prostriedok, ktorý je možné merať.
V prvej časti práce popisujeme viaceré modely konečných automatov, s rôznym množstvom nedeterminizmu a vysvetľujeme, aké sú medzi týmito triedami vzťahy. V druhej časti sa venujeme operáciám, ktoré sa pre modely NFA a DFA skúmali a skúmame tieto operácie pre ostatné triedy konečných automatov. V poslednej kapitole prezentujeme našu novú techniku na oddeľovanie tried konečných automatov. Pomocou tejto techniky dokazujeme tvrdenie SUFA $<_P$ FNA, ktoré bolo doteraz otvorené.
|
|---|