We study the problem stated as follows: which values in the range from log n to 2~n may be obtained as the state complexity of the reverse of a regular language represented by a minimal deterministic automaton of n states? In the main result of this paper we use an alphabet of size 2n - 2 to show that the entire range of complexities may be produced for any n. This considerably improves an analogous result from the literature that uses an alphabet of size 2~n. We also provide some partial results for the case of a binary alphabet.
展开▼
