×

On finite automata with limited nondeterminism. (English) Zbl 0923.68090

Summary: We develop a new algorithm for determining if a given nondeterministic finite automaton is limited in nondeterminism. From this, we show that the number of nondeterministic moves of a finite automaton, if limited, is bounded by \(2^n-2\) where \(n\) is the number of states. If the finite automaton is over a one-letter alphabet, using Gohon’s result the number of nondeterministic moves, if limited, is less than \(n^2\). In both cases, we present families of finite automata demonstrating that the upper bounds obtained are almost tight. We also show that the limitedness problem of the number of nondeterministic moves of finite automata is PSPACE-hard. Since the problem is already known to be in PSPACE, it is therefore PSPACE-complete.

MSC:

68Q45 Formal languages and automata
Full Text: DOI