Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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

share|improve this question
2  
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 at 5:47

1 Answer 1

up vote 7 down vote accepted

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

share|improve this answer
    
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. –  jmite May 7 at 20:22
1  
@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. –  Patrick87 May 7 at 20:51

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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