Ist die Umkehrung eines minimalen DFA auch minimal?

Die Frage steht so ziemlich im Titel. Gibt es überhaupt eine Zeit , wo einige Sprache kann durch eine minimale DFA mit akzeptiert werden n Staaten, sondern L R , die Umkehrung der L kann von einem DFA mit akzeptiert m Staaten, in denen m < n ?$L$$n$$L^R$$L$$m$$m<n$

Der minimale DFA, der die Umkehrung der Sprache akzeptiert, kann kleiner sein. Betrachten Sie die endliche Sprache Die Wörter ϵ , 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$inäquivalenten sind, so dass jeder DFA für mindestens 12 Staaten erfordert; Tatsächlich gibt es einen DFA mit genau 12 Staaten. Die umgekehrte Sprache L R = 2 ( 0 + 1 ) 2 + 1 ( 0 + 2 ) 2 + 0 ( 1 + 2 ) 2 wird von einem DFA mit nur 9 Zuständen akzeptiert: ein Anfangszustand, Zustände, die dem Anfangszustand 0 , 1 entsprechen , 2 , Zustände entsprechend der anfänglichen 0 ( 1 + 2 ) $L$ $$L^R = 2(0+1)^2 + 1(0+2)^2 + 0(1+2)^2$$ $0,1,2$ einen akzeptierenden Zustand und einen Fehlerzustand; Dies ist auch der optimale DFA, da ϵ , 0 , 1 , 2 , 01 , 12 , 20 , 011 , 000 nicht äquivalent sind.$0(1+2),1(0+2),2(0+1)$$\epsilon,0,1,2,01,12,20,011,000$

Zusammenfassend erfordert der minimale DFA für 12 Zustände, während der für L R nur 9 Zustände erfordert.$L$$L^R$

$L$$L^R$