Transition complexity of language operations

AbstractThe number of transitions required by a nondeterministic finite automaton (NFA) to accept a regular language is a natural measure of the size of that language. There has been a significant amount of work related to the trade-off between the number of transitions and other descriptional complexity measures for regular languages. In this paper, we consider the effect of language operations on the number of transitions required to accept a regular language. This work extends previous work on descriptional complexity of regular language operations, in particular, under the measures of deterministic state complexity, nondeterministic state complexity and regular expression size