Size of Nondeterministic and Deterministic Automata for Certain Languages.
Raitis Ozols, Rūsiņš Freivalds, Laura Mančinska, Māris Ozols · 2005
Abstract. In the theory of automata the question about difference between the size of deterministic and nondeterministic automata which recognize the same language is of great importance. However, this problem has been studied mainly in case when input alphabet consists of at least 2 letters. In this paper some special kind of languages in one letter alphabet will be discussed and the estimate of the number of states required for deterministic and nondeterministic automata to accept these languages will be made. For one of these languages nondeterministic automaton with ≤ ⎡ n ⎤ + 1 states can be built, but for other with 2 22)ln(ln ln85,0 lnln ln8,1 n n n n ⋅+⋅ ≤ states, where n is the number of states required for the corresponding deterministic automaton. Conference: FCS’05.