The state complexity of L-2 and L-k
We show that if M is a DFA with n states over an alphabet with at least two letters and L = L(M). then the worst-case state complexity of L-2 is n2(n) - 2(n-1). If, however, M is a DFA over a unary alphabet. then the worst-case state complexity of L-k is kn - k + 1 for all k >= 2. (c) 2006 Elsevier B.V. All rights reserved.
state complexity formal languages