Succinctness analysis of finite automaton models - Erdoğan, Emre. (Thesis (M.S.) - Bogazici University. Institute for Graduate Studies in Science and Engineering, 2017., 2017)
Finite state automaton, or ﬁnite automaton, is a mathematical model of compu tation and has been one of the most studied models in automata theory. Throughout the years, many diﬀerent types of ﬁnite state automata are proposed, such as deter ministic, nondeterministic, probabilistic, and quantum automata. Furthermore, the important questions that how they are related to each other, and how they are related to formal languages, have been a subject of intensive research. In this thesis, we study the succinctness properties of various ﬁnite automata. First, we thoroughly study the topic of simulating various ﬁnite automata by deter ministic ﬁnite automata. Second, we work with three diﬀerent families of regular languages and we provide the various minimal automata (i.e. minimal in the sense of the number of states used) deciding them. Third, we provide a descriptive form called “Unary Finite Periodic Form”, or shortly UFPF, to eﬃciently describe regu lar languages over unary alphabets and we introduce algorithms to show the eﬃcient realization of closure properties of UFPF.
Keywords: Sequential machine theory.