State complexity of power

The number of states in a deterministic finite automaton (DFA) recognizing the language Lk, where L is regular language recognized by an n-state DFA, and k⩾2 is a constant, is shown to be at most n2(k−1)n and at least (n−k)2(k−1)(n−k) in the worst case, for every n>k and for every alphabet of at least six letters. Thus, the state complexity of Lk is Θ(n2(k−1)n). In the case k=3 the corresponding state complexity function for L3 is determined as with the lower bound witnessed by automata over a four-letter alphabet. The nondeterministic state complexity of Lk is demonstrated to be nk. This bound is shown to be tight over a two-letter alphabet.