ON MEASURING NONDETERMINISM IN REGULAR LANGUAGES

It is well known that allowing nondeterminism in a finite automaton can produce in the most extreme case an exponential savings in the number of states required to recognize a regular language. This paper studies situations intermediate between forbidding nondeterminism and allowing it. The amount of nondeterminism used by a finite automaton is quantified, so that the decrease in the size of the state space that occurs as the amount of nondeterminism that is permitted increases in increments can be studied. These intermediate situations are shown always to lie between two extremes:. (1) there are no savings as the amount of nondeterminism increases incrementally, so that savings occur only when the amount of nondeterminism becomes unlimited;. (2) each increment of nondeterminism results in additional savings, the number s of states decreasing approximately as s 1 i, until exponential savings have been achieved after about i = logs log log s increments. © 1990.