Master's thesis

State complexity of partially nondeterministic automata - Nondeterministic choice of initial states

Author:

Bc. Šimon Huraj

Thesis supervisor:

RNDr. Juraj Šebej, PhD.

Goals:

  1. Develop a program that accepts an automaton as input and generates all automata with various choices of initial states. Expand this program to generate all n-state automata. Additionally, create a program capable of determinizing and minimizing the automaton to ascertain the state complexity of the language it represents. Furthermore, ensure that the program is designed to leverage parallel computing.
  2. Investigate the deterministic state complexity of automata represented by nondeterministic automata, where the only nondeterminism is from a choice of initial states.
  3. Examine the worst-case state complexity identified in 2.
  4. Explore the range of all obtainable state complexities from 2.
  5. Study the average state complexity from 2.

Literature

Markus Holzer, Kai Salomaa, Sheng Yu: On the State Complexity of k-Entry Deterministic Finite Automata. J. Autom. Lang. Comb. 6(4): 453-466 (2001)

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)

M. Krausová, Prefix-free regular languages: closure properties, difference, and left quotient, in: Z. Kotásek, et al. (Eds.), Proc. MEMICS 2011, in: LNCS, vol.7119, Springer, Heidelberg, 2012, pp.114–122.

Jozef Jirásek, Galina Jirásková, Monika Krausová, Peter Mlynárcik, Juraj Sebej: Prefix-free languages: Left and right quotient and reversal. Theor. Comput. Sci. 610: 78-90 (2016)