Minimizarea DFA

În Teoria automatelor (ramura informatică ) procesul care transformă un automat determinat determinist dat (pe scurt DFA) în DFA echivalent care are cel mai mic număr de stări se numește minimizarea unui DFA . Se spune că două DFA sunt echivalente dacă recunosc același limbaj formal . Există mai mulți algoritmi care produc DFA minim pornind de la unul dat, cu metode și complexitate diferite.

DFA minim

Există, pentru fiecare limbă obișnuită care poate fi acceptată de un DFA, un singur automat automat , adică un DFA care are numărul minim de stări. ^[1] Lucrul la automatul minim este convenabil din punct de vedere al complexității de calcul pentru acei algoritmi care îl utilizează în cele mai variate scopuri, cum ar fi potrivirea modelelor .

Pentru a reduce un DFA, în acesta sunt identificate două tipuri de stări, care pot fi unite sau eliminate fără a afecta limba acceptată de automatul însuși:

Stări inaccesibile : stări ale automatului la care în niciun caz nu se poate ajunge din starea inițială; adică stări (altele decât starea inițială) care nu au tranziții de intrare sau stări în care fiecare tranziție de intrare începe dintr-o stare inaccesibilă.
Stări nedistinguibile : stări care nu pot fi distinse de un alt stat prin oricare dintre șirurile posibile ale limbajului.

Minimizarea are loc în trei pași, în care stările de mai sus sunt eliminate sau unite între ele. Întotdeauna culminează cu eliminarea stărilor care nu se pot distinge, deoarece aceasta este cea mai scumpă operațiune.

Stări inaccesibile

Este

{\mathcal {A}}=(Q,\Sigma ,\delta ,q_{0},T)

{\ displaystyle {\ mathcal {A}} = (Q, \ Sigma, \ delta, q_ {0}, T)}

{\ displaystyle {\ mathcal {A}} = (Q, \ Sigma, \ delta, q_ {0}, T)}

un automat determinist complet. În această definiție, $Î$ ${\ displaystyle Q}$ $Î$ este setul de stări, $\Sigma$ ${\ displaystyle \ Sigma}$ $\ Sigma$ este alfabetul, $\delta$ ${\ displaystyle \ delta}$ $\ delta$ este funcția de tranziție care mapează o stare și un simbol alfabet la o stare, $q_{0}$ ${\ displaystyle q_ {0}}$ $q_0$ este starea inițială e $T.$ ${\ displaystyle T}$ $T.$ este setul de acceptare a stărilor terminale.

Două state $p$ ${\ displaystyle p}$ $p$ Și $q$ ${\ displaystyle q}$ $q$ aparținând $Î$ ${\ displaystyle Q}$ $Î$ , se spune că nu se pot distinge dacă toate cuvintele $w$ ${\ displaystyle w}$ $w$ recunoscut după ${\mathcal {A}}$ ${\ displaystyle {\ mathcal {A}}}$ ${\ mathcal {A}}$ începând de la $p$ ${\ displaystyle p}$ $p$ sunt recunoscute și începând de la $q$ ${\ displaystyle q}$ $q$ si invers. În mod formal, dacă pentru fiecare cuvânt $w$ ${\ displaystyle w}$ $w$ :

p\cdot w\in T\iff q\cdot w\in T

{\ displaystyle p \ cdot w \ in T \ if q \ cdot w \ in T}

{\ displaystyle p \ cdot w \ in T \ if q \ cdot w \ in T}

.

Două stări sunt separabile dacă nu sunt inseparabile. Se aplică următorul criteriu de minimizare:

Un automat finit determinist complet și accesibil este minim dacă și numai dacă stările sale sunt separabile două câte două.

Echivalența Nerode este relația notată $\sim$ ${\ displaystyle \ sim}$ $\ sim$ , pe setul de stări și definit de

q\sim q'\iff L_{q}({\mathcal {A}})=L_{q'}({\mathcal {A}})

{\ displaystyle q \ sim q '\ if L_ {q} ({\ mathcal {A}}) = L_ {q'} ({\ mathcal {A}})}

{\ displaystyle q \ sim q '\ if L_ {q} ({\ mathcal {A}}) = L_ {q'} ({\ mathcal {A}})}

.

Două stări echivalente pentru relația anterioară nu se pot distinge și invers. Un automat este minim atunci când echivalența lui Nerode este egalitatea.

Algoritm pentru calcularea stărilor accesibile / inaccesibile

Statul $p$ ${\ displaystyle p}$ $p$ a unui automat finit determinist ${\mathcal {A}}=(Q,\Sigma ,\delta ,q_{0},T)$ ${\ displaystyle {\ mathcal {A}} = (Q, \ Sigma, \ delta, q_ {0}, T)}$ ${\ displaystyle {\ mathcal {A}} = (Q, \ Sigma, \ delta, q_ {0}, T)}$ este inaccesibil dacă nu există un cuvânt $w\in \Sigma ^{*}$ ${\ displaystyle w \ in \ Sigma ^ {*}}$ ${\ displaystyle w \ in \ Sigma ^ {*}}$ pentru care $p=\delta (q_{0},w)$ ${\ displaystyle p = \ delta (q_ {0}, w)}$ ${\ displaystyle p = \ delta (q_ {0}, w)}$ . Notăm aici $\delta ^{*}$ ${\ displaystyle \ delta ^ {*}}$ ${\ displaystyle \ delta ^ {*}}$ extinderea funcției la toate șirurile. Stările accesibile pot fi obținute cu următorul algoritm:

 let reachable_states : = { q0 };
lasa state_nou : = { q0 };
face {
    temp : = ∅ ;
    pentru fiecare q din new_states do
        pentru fiecare c din Σ do
            temp : = temp ∪ { p astfel încât p = δ ( q , c )};
        sfârșit ;
    sfârșit ;
    new_states : = temp \ reachable_states ;
    reachable_states: = reachable_states ∪ new_states;
} while ( new_states ≠ ∅ );
unreachable_states : = Q \ reachable_states ;

Stările inaccesibile pot fi eliminate din DFA fără a afecta limba pe care o acceptă.

Notă

^ Alfred V. Aho, Monia S. Lam, Ravi Sethi, Jeffrey D. Ullman, Capitolul 3.9.6 - Minimizarea numărului de state ale unui DFA , în compilatoare. Principii, tehnici și instrumente , ediția a II-a, Pearson Education, 2006.

[1] Alfred V. Aho, Monia S. Lam, Ravi Sethi, Jeffrey D. Ullman, Capitolul 3.9.6 - Minimizarea numărului de state ale unui DFA , în compilatoare. Principii, tehnici și instrumente , ediția a II-a, Pearson Education, 2006.

[1]