Conversia AFN în AFD

Vom vedea cum se convertește un automat nedeterminist într-un automat determinist, demonstrând astfel că puterea de calcul a automatelor nedeterministe și a celor deterministe este echivalentă.

Ideea de bază

Fie un automat nedeterminist ⟨Q_N, Σ_N, δ_N, q₀, F_N⟩ fără ε-tranziții. Construim un automat determinist ⟨Q_D, Σ_D, δ_D, p₀, F_D⟩ astfel încât

• Q_D ⊆ 2^Q_N
• Σ_D = Σ_N
• p₀ = {q₀}
• F_D = {Q ∈ Q_D | Q ∩ F_N ≠ ∅}

Funcția de tranziție δ_D o definim astfel:

$$\mathrm{\forall }Q\in Q_D,a\in {\mathrm{\Sigma }}_D:{\delta }_D(Q,a)=\bigcup _{q\in Q}{\delta }_N(q,a)$$

Ce înseamnă asta? Un automat nedeterminist se poate afla simultan în mai multe stări, deci, de exemplu, putem ajunge în situația în care automatul nostru nedeterminist este în stările {q₀, q₁}. Citind următorul simbol, de exemplu 1, putem ajunge în mulțimea de stări {q₀, q₂, q₃}. În versiunea deterministă a aceluiași automat, acest lucru se reflectă prin faptul că creăm două stări, le denumim {q₀, q₁} și {q₀, q₂, q₃} și introducem între ele o tranziție pentru simbolul 1. Formal, trecem dintr-o stare în alta, dar datorită denumirii vom ști că în automatul nedeterminist ne-am fi aflat în două, respectiv în trei stări.

Exemplu

Fie acest automat nedeterminist:

Pentru a construi automatul determinist, trebuie mai ales să construim noua funcție de tranziție. Ne ajută un tabel în care notăm toate tranzițiile. La început, tabelul arată astfel:

$$\begin{array}{ccc}\text{stare}/\text{simbol}& 0& 1\\ \left\{q_0\right\}\end{array}$$

În coloana din stânga vom avea, la sfârșitul algoritmului, toate stările automatului determinist. Tabelul completat va defini apoi funcția de tranziție. Acum scriem în tabel în ce stări ajungem dacă ne aflăm în starea {q₀} și la intrare avem simbolurile 0 și 1.

$$\begin{array}{ccc}\text{stare}/\text{simbol}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\end{array}$$

Din starea q₀ pleacă pentru simbolul 0 o tranziție doar spre starea q₁, în timp ce pentru simbolul 1 pleacă spre stările q₁ și q₂. Acum adăugăm în tabel două stări noi: {q₁} și {q₁, q₂}. De ce? Ori de câte ori completăm în tabel o mulțime de stări pe care nu o avem încă în coloana din stânga, o adăugăm și acolo.

$$\begin{array}{ccc}\text{stare}/\text{simbol}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \left\{q_1\right\}\\ \{q_1,q_2\}\end{array}$$

și completăm din nou. La starea {q₁, q₂} nu trebuie să uităm să verificăm ambele stări, adică mulțimea stărilor în care ajungem din starea q₁, reunită cu cea în care ajungem din starea q₂.

$$\begin{array}{ccc}\text{stare}/\text{simbol}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \left\{q_1\right\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_1,q_2\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\end{array}$$

Am obținut câteva stări noi, pe care trebuie să le adăugăm în tabel:

$$\begin{array}{ccc}\text{stare}/\text{simbol}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \left\{q_1\right\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_1,q_2\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_0,q_1,q_3\}\\ \{q_0,q_3\}\end{array}$$

…și completăm iar tranzițiile:

$$\begin{array}{ccc}\text{stare}/\text{simbol}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \left\{q_1\right\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_1,q_2\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_0,q_1,q_3\}& \{q_0,q_1,q_3\}& \{q_0,q_1,q_2,q_3\}\\ \{q_0,q_3\}& \left\{q_1\right\}& \{q_1,q_2\}\end{array}$$

Stările {q₀, q₁, q₃}, {q₁} și {q₁,q₂} le avem deja, deci adăugăm doar starea {q₀,q₁,q₂,q₃}.

$$\begin{array}{ccc}\text{stare}/\text{simbol}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \left\{q_1\right\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_1,q_2\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_0,q_1,q_3\}& \{q_0,q_1,q_3\}& \{q_0,q_1,q_2,q_3\}\\ \{q_0,q_3\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \{q_0,q_1,q_2,q_3\}& \{q_0,q_1,q_3\}& \{q_0,q_1,q_2,q_3\}\end{array}$$

Nu am mai adăugat nicio stare nouă, deci tabelul este completat. Acum rămâne doar să construim diagrama. Stările automatului determinist sunt în prima coloană, iar tranzițiile pentru simbolurile 0 și 1 în următoarele. Orice stare care conține o stare finală din automatul inițial va fi stare finală și în acest automat. Adică orice stare care conține q₃ va fi stare finală. Automatul va arăta astfel:

Putem verifica faptul că automatul funcționează cu adevărat corect. Încercăm să acceptăm cuvântul 11001. În automatul determinist vom merge pe drumul

$$q_0{\to }^1{q}_1,q_2{\to }^1{q}_0,q_3{\to }^0{q}_1{\to }^0{q}_0,q_1,q_3{\to }^1{q}_0,q_1,q_2,q_3$$

iar automatul ar accepta cuvântul, deoarece ultima stare {q₀, q₁, q₂, q₃} este finală. În automatul nedeterminist am ajunge, în timpul simulării, în aceleași stări, adică am porni din starea q₀ și, pentru simbolul 1, am ajunge în stările {q₁, q₂}. Următorul simbol 1 ne-ar duce în stările {q₀,q₃} și așa mai departe pentru celelalte stări. La final ne-am afla în toate stările {q₀, q₁, q₂, q₃} și automatul ar accepta cuvântul.

Surse

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools