<p>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.</p>

<p>This was first observed by Maslov in 1970, and rediscovered by Yu, Zhuang, and K. Salomaa in their paper, "The state complexities of some basic operations on regular languages", TCS 125 (1994), 315-328.</p>

CC BY-SA 3.0
2011-06-24T15:14:17.653Z
Thanks, Jeffrey! Is this automaton constructible in time less than the trivial $O(2^{n+m})$?
Aryeh
CC BY-SA 3.0
2011-06-24T15:16:39.203Z
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}$.
Jeffrey Shallit
CC BY-SA 4.0
2023-12-20T19:33:15.673Z
Just pointing out that there is a Wikipedia page which is a great resource for this kind of questions: https://en.wikipedia.org/wiki/State_complexity#Concatenation
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2011-06-24T15:06:32.893Z
2011-06-24T19:39:17.870Z
2011-06-24T19:39:17.870Z
Jeffrey Shallit
<p>There is <a href="http://rjlipton.wordpress.com/2009/08/17/on-the-intersection-of-finite-automata/">theoretical evidence</a> 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)?</p>

<cc.complexity-theory><fl.formal-languages><automata-theory><dfa>
Efficient concatenation of DFAs?
Aryeh
# Efficient concatenation of DFAs?

(Asked by: username_0 on 2011-06-24)

There is [theoretical evidence](http://rjlipton.wordpress.com/2009/08/17/on-the-intersection-of-finite-automata/) 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)?

**Tags:** cc.complexity-theory, fl.formal-languages, automata-theory, dfa


---

## 1 answers

### Answer by username_1 on 2011-06-24. Score: 21 | Accepted answer

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.

This was first observed by Maslov in 1970, and rediscovered by Yu, Zhuang, and K. Salomaa in their paper, "The state complexities of some basic operations on regular languages", TCS 125 (1994), 315-328.

> **Comments:**
> **username_0**: Thanks, Jeffrey! Is this automaton constructible in time less than the trivial $O(2^{n+m})$?  
> **username_1**: 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}$.  
> **username_2**: Just pointing out that there is a Wikipedia page which is a great resource for this kind of questions: https://en.wikipedia.org/wiki/State_complexity#Concatenation  

---

