State Complexity of Nondeterministic Finite Automata with Limited Nondeterminism
Abstract
Various approaches of quantifying nondeterminism in nondeterministic
finite automata (NFA) are considered.
We consider nondeterministic finite automata
having finite tree width (ftw-NFA) where
the computation on any input string has a constant number
of branches. We give effective characterizations of
ftw-NFAs and a tight bound for determinizing
an ftw-NFA A as a function of the tree width and the
number of states of A. We introduce a lower bound
technique for ftw-NFAs.
We study the interrelationships between various measures
of nondeterminism for finite automata. We define the trace measure
which is a new approach of quantifying nondeterminism.
The trace is defined in
terms of the maximum product of the degrees of nondeterministic
choices in any computation. We establish
upper and lower bounds for the trace of an NFA in
terms of its tree width.
It is known that an NFA with n states and branching k
can be simulated by a deterministic finite automaton
with multiple initial states (MDFA) having kn states.
We give a lower bound (k/(1+\logk))n for
the size blow-up of this conversion.
We also consider bounds for the number
of states an MDFA needs to simulate a given NFA of finite
tree width.
We consider unary NFA employing limited
nondeterminism. We show that for unary regular languages,
minimal ftw-NFAs can always be found in Chrobak normal form. A similar property
holds with respect to other measures of nondeterminism.
The latter observation is used to establish,
for a given unary regular language, relationships between
the sizes of minimal NFAs where the nondeterminism
is limited in various ways.
We study also the state complexity of language operations for
unary NFAs with limited nondeterminism. We consider the
operations of concatenation, Kleene star, and complement.
We give upper bounds for the state complexity of these
language operations and lower bounds that are fairly close
to the upper bounds.
Finally, we show that the branching measure
(J. Goldstine, C. Kintala, D. Wotschke, Inf. and Comput vol 86, 1990,
179-194) of a unary NFA
is always either bounded
by a constant or has an exponential growth rate.