# Is the reversal of a minimal DFA also minimal?

The question is pretty much in the title. Is there ever a time where some language $L$ can be accepted by a minimal DFA with $n$ states, but $L^R$, the reversal of $L$, can be accepted by a DFA with $m$ states, where $m<n$?

• The reverse of a DFA is not even necessarily deterministic. A DFA that accepts the regex AAA+ has a terminal state with two inbound arrows with the same label. – Ian May 8 '14 at 5:47

The minimal DFA accepting the reversal of the language can be smaller. Consider the finite language $$L = (0+1)^22+(0+2)^21+(1+2)^20.$$ The words $\epsilon,0,1,2,00,01,02,11,12,22,000,001$ are inequivalent, so any DFA for $L$ requires at least 12 states; in fact there is a DFA with exactly 12 states. The reverse language $$L^R = 2(0+1)^2 + 1(0+2)^2 + 0(1+2)^2$$ is accepted by a DFA with only 9 states: an initial state, states corresponding to initial $0,1,2$, states corresponding to initial $0(1+2),1(0+2),2(0+1)$, an accepting state and a fail state; this is also the optimal DFA, since $\epsilon,0,1,2,01,12,20,011,000$ are inequivalent.
Summarizing, the minimal DFA for $L$ requires 12 states, while the one for $L^R$ requires only 9 states.
As jmite mentions in their comment, for NFAs with multiple starting states this phenomenon can't happen, since if you flip the direction of all arrows in a NFA for $L$ then you get a valid NFA for $L^R$.