Š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:

  1. Študovať známe výsledky stavovej zložitosti unárnych operácii hviezdička, plus a štvorec.
  2. Vytvoriť program na generovanie unárnych automatov.
  3. Skúmať stavovú zložitosť automatov generovaných v bode 2. z dôrazom na štrukturálne vlastnosti:
    1. dĺžka cyklov
    2. počet koncových stavov
  4. 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)