STATE COMPLEXITY OF CONCATENATION AND COMPLEMENTATION
Jozef Štefan Jirásek, Galina Jirásková, Alexander Szabari · International Journal of Foundations of Computer Science · 2005
We investigate the state complexity of concatenation and the nondeterministic state complexity of complementation of regular languages. We show that the upper bounds on the state complexity of concatenation are also tight in the case that the first automaton has more than one accepting state. In the case of nondeterministic state complexity of complementation, we show that the entire range of complexities, up to the known upper bound can be produced.