The Complexity of Languages Resulting from the Concatenation Operation
Galina Jirásková, Alexander Szabari, Juraj Šebej · Journal of automata, languages and combinatorics · 2017
We prove that for all $m,n,$ and $\alpha$ with $1 \le \alpha \le f(m,n)$, where $f(m,n)$ is the state complexity of the concatenation operation, there exist a minimal $m$-state deterministic finite automaton $A$ and a minimal $n$-state deterministic finite automaton $B$, both defined over an alphabet $\Sigma$ with $|\Sigma|\le 2n+4$, such that the minimal deterministic finite automaton for the language $L(A)L(B)$ has exactly $\alpha$ states. This improves a similar result in the literature that uses an exponential alphabet.