Obtaining tight upper-bounds for the state complexities of DFA operations

The authors consider the state complexity of basic operations of regular languages. They show that the number of states that is sufficient and necessary in the worst case for a deterministic finite automaton (DFA) to accept the catenation of an m-state DFA language and an n-state DFA language is exactly m2ⁿ-2^n-1, for m, n>1. The result of 2^n-1+2^n-2 states is obtained for the star of an n-state DFA language, n>1. State complexities for other basic operations and for regular languages over a one-letter alphabet are also studied