# Efficient concatenation of DFAs?

There is theoretical evidence that the naive cartesian-product construction for the intersection of DFAs is "the best we can do". What about the concatenation of two DFAs? The trivial construction involves converting each DFA into an NFA, adding an epsilon-transition and determinizing the resulting NFA. Can we do better? Is there a known bound on the size of the minimal concatenation DFA (in terms of the sizes of the "prefix" and "suffix" DFAs)?

Yes - it is known that there exist DFA's of $m$ and $n$ states, respectively, such that the minimal DFA for the concatenation of the corresponding languages has $m*2^n - 2^{n-1}$ states, which matches the known upper bound.
• Thanks, Jeffrey! Is this automaton constructible in time less than the trivial $O(2^{n+m})$? Jun 24 '11 at 15:14
• If you look at the paper I cited you will see the construction, and it looks to me that it can be constructed in essentially the same time as the number of states, $m*2^n - 2^{n-1}$. Jun 24 '11 at 15:16