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$ ?

— jmite
źródło

Odwrotność DFA niekoniecznie jest deterministyczna. DFA, który akceptuje regex AAA +, ma stan końcowy z dwiema strzałkami przychodzącymi z tą samą etykietą.

— Ian

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

L = (0 + 1)^{2} 2 + (0 + 2)^{2} 1 + (1 + 2)^{2} 0.

$L = (0+1)^22+(0+2)^21+(1+2)^20.$ Słowa

ϵ, 0, 1, 2, 00, 01, 02, 11, 12, 22, 000, 001

$\epsilon,0,1,2,00,01,02,11,12,22,000,001$ są nierówne, więc każdy DFA dla

L

$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}

$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

$0,1,2$ , stany odpowiadające początkowej

0 (1 + 2), 1 (0 + 2), 2 (0 + 1)

$0(1+2),1(0+2),2(0+1)$ , stan akceptacji i stan awarii; jest to również optymalny DFA, ponieważ

ϵ, 0, 1, 2, 01, 12, 20, 011, 000

$\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$ .

— Yuval Filmus
źródło

Dzięki! Jakoś sobie przypomniałem, że możesz odwrócić DFA i (bezpośrednio) odzyskać DFA, myślę, że pomyliłem go z dopełnieniem.

— jmite

@jmite Miałem ten sam pierdnięcie mózgu i napisałem elegancki dowód, zaprzeczając błędnej odpowiedzi. :) To uzupełnienie działa tak, jak myślałem, a nie odwrócenie. Ups

— Patrick87