9
$\begingroup$

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$?

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Ian May 8 '14 at 5:47
7
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Thanks! I somehow got it in my head that you could reverse a DFA and (directly) get a DFA back, I think I got it confused with complement. $\endgroup$ – jmite May 7 '14 at 20:22
  • 1
    $\begingroup$ @jmite I had the same brain fart, and typed out an elegant proof by contradiction of the wrong answer. :) It's complement that works like I thought, not reversal. Oops. $\endgroup$ – Patrick87 May 7 '14 at 20:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.