¿La inversión de un DFA mínimo también es mínima?

La pregunta está más o menos en el título. ¿Hay algún momento en que un lenguaje puede ser aceptado por un DFA mínimo con estados, pero , la reversión de , puede ser aceptado por un DFA con estados, donde$L$$n$$L^R$$L$$m$$m<n$ ?

El DFA mínimo que acepta la inversión del lenguaje puede ser menor. Considere el lenguaje finito Las palabras ϵ , 0 , 1 , 2 , 00 , 01 , 02 , 11 , 12 , 22 , 000 ,

$$L = (0+1)^22+(0+2)^21+(1+2)^20.$$ $\epsilon,0,1,2,00,01,02,11,12,22,000,001$no son equivalentes, por lo que cualquier DFA para requiere al menos 12 estados; de hecho, hay un DFA con exactamente 12 estados. El lenguaje inverso L R = 2 ( 0 + 1 ) 2 + 1 ( 0 + 2 ) 2 + 0 ( 1 + 2 ) 2 es aceptado por un DFA con solo 9 estados: un estado inicial, estados correspondientes a los iniciales 0 , 1 , 2 , estados correspondientes al 0 inicial ( 1 + 2 ) $L$ $$L^R = 2(0+1)^2 + 1(0+2)^2 + 0(1+2)^2$$ $0,1,2$ , un estado de aceptación y un estado de falla; este también es el DFA óptimo, ya que ϵ , 0 , 1 , 2 , 01 , 12 , 20 , 011 , 000 no son equivalentes.$0(1+2),1(0+2),2(0+1)$$\epsilon,0,1,2,01,12,20,011,000$

En resumen, el DFA mínimo para requiere 12 estados, mientras que el de L R requiere solo 9 estados.$L$$L^R$

$L$$L^R$