On the State Complexity of the Shuffle of Regular Languages

Janusz Brzozowski, Galina Jirásková, Bo Liu +2

We investigate the shuffle operation on regular languages represented by complete deterministic finite automata. We prove that $f(m,n)=2^{mn-1} + 2^{(m-1)(n-1)}(2^{m-1}-1)(2^{n-1}-…