Štrukturálne vlastnosti a stavová zložitosť unárnych operácii na konečnostavových automatoch
Vedúci práce:
RNDr. Juraj Šebej, PhD.
Autor:
Bc. Šimon Javorský
Ciele práce:
- Študovať známe výsledky stavovej zložitosti unárnych operácii hviezdička, plus a štvorec.
- Vytvoriť program na generovanie unárnych automatov.
- Skúmať stavovú zložitosť automatov generovaných v bode 2. z dôrazom na štrukturálne vlastnosti:
- dĺžka cyklov
- počet koncových stavov
- Skúmať rovnaký problém ako v bode 3. pre binárne automaty.
Literatúra:
- Galina Jirásková: The Ranges of State Complexities for Complement, Star, and Reversal of Regular Languages. Int. J. Found. Comput. Sci. 25(1): 101- (2014)
- Kristína Cevorová, Galina Jirásková, Ivana Krajnáková: On the Square of Regular Languages. CIAA 2014: 136-147 (2014)
- John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Introduction to automata theory, languages, and computation - international edition (2. ed). Addison-Wesley (2003)
- Jacques Sakarovitch: Elements of Automata Theory. Cambridge University Press 2009, ISBN 978-0-521-84425-3, pp. I-XXIV, 1-758 (2009)
Priebeh práce:
- oboznámenie sa s problematikou ✔
- analýza prístupu ku generovaniu automatov ✔
- implementovanie algoritmov ✔
- generovanie výsledkov ✔
- analýza výsledkov ✔
- formulácia dôkazov ✔
Súbory:
Prezentácia SDI1a (.pdf)Prezentácia SDI1b (.pdf)