THE RANGES OF STATE COMPLEXITIES FOR COMPLEMENT, STAR, AND REVERSAL OF REGULAR LANGUAGES

摘要

We examine the deterministic and nondeterministic state complexity of complements, stars, and reversals of regular languages. Our results are as follows: (1) The nondeterministic state complexity of the complement of an n-state nfa language over a five-letter alphabet may reach each value from log n to 2~n. (2) The state complexity of the star (reversal) of an n-state dfa language over a growing alphabet may reach each value from 1 to 3/4·2~n (from log n to 2~n, respectively). (3) The nondeterministic state complexity of the star (reversal) of an n-state nfa binary language may reach each value from 1 to n + 1 (from n - 1 to n + 1, respectively). We also obtain some partial results on the nondeterministic state complexity of complements of binary regular languages. As a bonus, we get an exponential number of values that are non-magic in the binary case.