Reversal of regular languages and state complexity.
Juraj Šebej · ITAT · 2010
We study the state complexity of languages that can be obtained as reversals of regular languages represented by deterministic final automata. We show that the state complexity of the reversal of a regular language with state complexity n is between logn and 2. We first prove that the upper bound is tight in the ternary case. Then we present binary languages reaching this upper bound on the reversal. We also obtain some other partial results in the binary case.