patternMinor
Is the reversal of a minimal DFA also minimal?
Viewed 0 times
dfathealsoreversalminimal
Problem
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$?
Solution
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$.
$$ 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$.
Context
StackExchange Computer Science Q#24504, answer score: 7
Revisions (0)
No revisions yet.