Unary NFAs, Limited Nondeterminism, and Chrobak Normal Form
Alexandros Palioudakis, Kai Salomaa and Selim G. Akl
We consider unary finite automata employing limited nondeterminism. We show that for a unary regular language, a state minimal finite tree width nondeterministic finite automaton (NFA) can always be found in Chrobak normal form. A similar property holds for state minimal finite ambiguity NFAs as well as for state minimal finite trace NFAs. The latter observation is used to establish relationships between classes of unary regular languages recognized by NFAs of given size where the nondeterminism is limited in various ways. Finally, we show that the branching measure of a unary NFA is always either bounded by a constant or has an exponential growth rate.
Keywords: Finite automata, limited nondeterminism, state complexity, unary regular languages