Ist die Umkehrung eines minimalen DFA auch minimal?

10

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 ?LnLRLmm<n

jmite
quelle
3
Die Umkehrung eines DFA ist nicht unbedingt deterministisch. Ein DFA, der den regulären Ausdruck AAA + akzeptiert, hat einen Terminalstatus mit zwei eingehenden Pfeilen mit derselben Bezeichnung.
Ian

Antworten:

7

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 , 001

L=(0+1)22+(0+2)21+(1+2)20.
ϵ,0,1,2,00,01,02,11,12,22,000,001inä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
LR=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)ϵ,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.LLR

LLR

Yuval Filmus
quelle
Vielen Dank! Ich habe es irgendwie in meinem Kopf verstanden, dass man einen DFA umkehren und (direkt) einen DFA zurückbekommen kann. Ich glaube, ich habe ihn mit Komplement verwechselt.
Jmite
1
@jmite Ich hatte den gleichen Hirnfurz und tippte einen eleganten Beweis durch Widerspruch zur falschen Antwort. :) Es ist eine Ergänzung, die so funktioniert, wie ich dachte, keine Umkehrung. Hoppla.
Patrick87