| Meno: | Ján
|
|---|
| Priezvisko: | Rosina
|
|---|
| Názov: | Nedeterminizmus v konečných automatoch
|
|---|
| Vedúci: | prof. RNDr. Branislav Rovan, PhD.
|
|---|
| Rok: | 2018
|
|---|
| Kľúčové slová: | nedeterministický konečný automat, deterministický konečný automat, jazyky definované podslovom, jazyky nad unárnou abecedou, ohraničené jazyky
|
|---|
| Abstrakt: | Je známe, že vo všeobecnosti pre daný nedeterministický konečný automat je pre zostrojenie ekvivalentného deterministického konečného automatu potrebných a postačujúcich exponenciálne veľa stavov. V tejto práci ukážeme, že pre vybrané podtriedy regulárnych jazykov je tento nárast stavovej zložitosti menší.
Pre nedeterministické konečné automaty overujúce iba výskyt daného podslova nie je potrebný žiadny nárast počtu stavov. Pre jazyky nad unárnou abecedou ukážeme, že tento nárast súvisí s vetvením grafu silne súvislých komponentov pre daný nedeterministický konečný automat. Napokon ukážeme, že pre ohraničené jazyky je nárast stavovej zložitosti deterministického konečného automatu k nedeterministickému väčší, ako tomu bolo pri jazykoch nad unárnou abecedou napriek ich dokázateľnému súvisu.
|
|---|