Lower bounds for the transition complexity of NFAs
We construct regular languages L-n, n >= 1, such that any NFA recognizing L-n needs Omega(nsc(L-n) center dot root nsc(L-n)) transitions. Here nsc(L-n) is the nondeterministic state complexity of L-n. Also, we study trade-offs between the number of states and the number of transitions of an NFA. We show that adding one additional state can result in significant reductions in the number of transitions and that there exist regular languages L-n, n >= 2, where the transition minimal NFA for L-n has more than c center dot nsc(L-n) states, for some constant c > 1. (C) 2008 Elsevier Inc. All rights reserved.
regular languages descriptional complexity nondeterministic finite automata finite projective planes