Czy odwrócenie minimalnego DFA jest również minimalne?

Pytanie jest prawie w tytule. Czy jest jakiś czas, kiedy jakiś język$L$ może być zaakceptowany przez minimalną DFA z $n$ stwierdza, ale $L^R$, odwrócenie $L$, może zostać zaakceptowany przez DFA za pomocą $m$ państwa, gdzie $m<n$?

Minimalna DFA akceptująca zmianę języka może być mniejsza. Rozważmy skończony język

$$L = (0+1)^22+(0+2)^21+(1+2)^20.$$ Słowa $\epsilon,0,1,2,00,01,02,11,12,22,000,001$ są nierówne, więc każdy DFA dla $L$wymaga co najmniej 12 stanów; w rzeczywistości istnieje DFA z dokładnie 12 stanami. Odwrotny język $$L^R = 2(0+1)^2 + 1(0+2)^2 + 0(1+2)^2$$ jest akceptowany przez DFA z tylko 9 stanami: stan początkowy, stany odpowiadające początkowi $0,1,2$, stany odpowiadające początkowej $0(1+2),1(0+2),2(0+1)$, stan akceptacji i stan awarii; jest to również optymalny DFA, ponieważ$\epsilon,0,1,2,01,12,20,011,000$ są nierówne.

Podsumowując, minimalny DFA dla $L$ wymaga 12 stanów, a ten dla $L^R$ wymaga tylko 9 stanów.

Jak wspomina w swoim komentarzu jmite, dla NFA z wieloma stanami początkowymi to zjawisko nie może się zdarzyć, ponieważ jeśli zmienisz kierunek wszystkich strzałek w NFA dla $L$ otrzymasz ważny NFA dla $L^R$.