Succinctness analysis of finite automaton models

Abstract

Finite state automaton, or finite automaton, is a mathematical model of compu tation and has been one of the most studied models in automata theory. Throughout the years, many different types of finite 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 finite automata. First, we thoroughly study the topic of simulating various finite automata by deter ministic finite automata. Second, we work with three different 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 efficiently describe regu lar languages over unary alphabets and we introduce algorithms to show the efficient realization of closure properties of UFPF.