Tight Lower Bound for the State Complexity of Shuffle of Regular Languages
Cezar Câmpeanu, Kai Salomaa, Sheng Yü · 2002
The upper bound for the state complexity of the shuffle of two regular languages is $2^{mn}-1$. We prove that this bound can be reached for some (not necessarily complete) deterministic finite automata With, respectively, $m$ and $n$ states. Our construction uses an alphabet of size 5.