Bachelor's thesis

Partially nondeterministic automata - Nondeterministic choice of initial states

Author:

Bc. Šimon Huraj

Thesis supervisor:

RNDr. Juraj Šebej, PhD.

Goals:

  1. To study known results of operations left quotient and right quotient.
  2. Create a program which takes automaton and generate all automata with various choose of initial states. Create a program which can determinize and minimize automaton to provide state complexity of language represented by particular automaton.
  3. Formulate hypotheses about state complexity of automata resulting by change on set of initial states.
  4. Generalize obtained hypotheses from 3. and prove their tightness.

Literature

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)