Automat finit nedeterminist

Automatul finit prezentat în capitolele anterioare (îl prescurtăm AF sau AFD) a fost întotdeauna determinist, ceea ce se vedea prin faptul că în fiecare moment era clar ce va face automatul. Acum ne vom ocupa de conceptul mai general al automatelor finite nedeterministe (le prescurtăm AFN), în care pot exista tranziții care pleacă din aceeași stare și sunt pentru același simbol.

Exemplu

Privește diagrama următorului automat:

Ce este neobișnuit la el? Faptul că din nodul q₀ pleacă două muchii pentru simbolul 0. Dacă încercăm să acceptăm cuvântul 001, ar părea că automatul nu va ști dacă trebuie să rămână în starea q₀ sau dacă trebuie să urmeze tranziția spre q₁. Un astfel de automat este nedeterminist.

Determinismul în acest sens înseamnă că în fiecare situație este clar ce va face automatul, nu există loc de ambiguitate. Automatul determinist are pentru fiecare stare și fiecare simbol o singură tranziție. Nedeterminismul înseamnă ambiguitate – dintr-o stare pot pleca, pentru același simbol, chiar și trei tranziții.

Și atunci, cum se decide automatul? Automatul nedeterminist alege întotdeauna (uneori spunem și „ghicește”) tranziția care duce la acceptarea cuvântului, dacă acest lucru este posibil.

Dacă introducem în automat cuvântul 001, automatul are aceste posibilități de a trata cuvântul:

$\begin{array}{r} q_{0} \to q_{0} \to q_{0} \to q_{0} \\ q_{0} \to q_{0} \to q_{1} \to q_{2} \end{array}$

plus posibilitățile în care nu citește tot cuvântul. În prima, a rămas mereu în starea q₀, ceea ce are desigur voie să facă, regulile de tranziție o permit. În a doua ramură a îndrăznit să meargă în alte stări și în cele din urmă a ajuns în starea q₂, care este finală. În această ramură automatul ar accepta cuvântul. Automatul nedeterminist alege întotdeauna de la sine ramura în care acceptă cuvântul, dacă o astfel de ramură există.

Cum reușește să aleagă de la sine ramura „favorabilă”? Ne putem imagina că automatul nedeterminist parcurge toate ramurile posibile și, dacă găsește o ramură în care acceptă cuvântul, atunci acceptă cuvântul. Cum ar putea parcurge toate ramurile? Pur și simplu, în momentul în care se află într-o stare din care pleacă n muchii pentru simbolul curent, automatul se copiază de n ori, iar fiecare copie merge pe alt drum. Astfel parcurgem treptat toate posibilitățile.

Reprezentarea calculului automatului prin arbore

Modificăm puțin automatul anterior:

Nedeterminismul rămâne în prima stare. Automatul anterior accepta toate cuvintele care se termină cu 01. Acest automat modificat acceptă toate cuvintele care conțin subcuvântul 01. Deci acceptă, de exemplu, cuvântul 101 sau 0101. Toate ramurile calculului le putem vizualiza ușor cu ajutorul unui arbore; de exemplu, pentru cuvântul 01010 arborele ar putea arăta astfel:

La început ne aflăm în starea inițială q₀. La intrare avem cuvântul 01010, primul caracter necitit este 0. Din starea q₀ pleacă două tranziții pentru simbolul 0, spre stările q₀ și q₁. Arborele va avea deci în acest nod doi descendenți: q₀ și q₁. În continuare citim simbolul 1. Aici nu există nicio ambiguitate, ne mutăm în stările q₀ și q₂. Apoi citim caracterul 0, iar în ramura stângă apare din nou ambiguitate, împărțim calculul în alte două ramuri. Într-una rămânem din nou în q₀, iar în cealaltă mergem în q₁. Și așa mai departe.

Observă că în total două ramuri se termină în starea q₂, adică într-o stare finală. Există două ramuri de calcul prin care automatul poate accepta cuvântul dat. Acest automat ar accepta deci cuvântul 01010. Putem încerca să construim un arbore asemănător pentru cuvântul 1000.

Calculul fie rămâne în starea q₀, fie trece în starea q₁, dar de acolo nu mai are unde să meargă, pentru că la intrare au rămas doar zerouri, iar starea q₁ are tranziție doar pentru simbolul 1. Nicio ramură a calculului nu se termină într-o stare finală, deci automatul nu acceptă cuvântul 1000.

ε-tranziții

În automatele nedeterministe putem folosi în plus și ε-tranziții. Acestea sunt tranziții pe care le putem face oricare ar fi simbolul de la intrare, fără să citim vreun simbol din cuvânt. Cum am putea scrie un automat nedeterminist care să accepte cuvântul vid, toate cuvintele formate doar din cifre 1 și cuvintele de forma (10)ⁿ, adică 10, 1010, …?

Am împărțit automatul în două „subautomate”. Cel de sus se ocupă de recunoașterea cuvintelor formate din 1, cel de jos se ocupă de cuvintele de forma (10)ⁿ. Încercăm să acceptăm cuvântul 111. La început automatul se află în starea q₀ și are la intrare cuvântul 111. Pentru că are la dispoziție ε-tranziții, poate decide să treacă în starea q₁ sau q₂, după cum îi convine. Vedem că îi va conveni să treacă în starea q₁. Automatul trece acolo. Cu toate acestea, la intrare are în continuare cuvântul 111! Abia în acest moment începe să citească simbolurile din cuvânt și să treacă din starea q₁ din nou în q₁, până când citește tot cuvântul și îl acceptă.

Dacă am încerca să acceptăm 1010, automatul ar trece la început în starea q₂ și abia de acolo ar începe să prelucreze simbolurile și ar accepta din nou cuvântul.

Pentru cuvântul 1100 automatul ar putea face orice, nu are cum să accepte un astfel de cuvânt.

ε-tranzițiile și nedeterminismul ne ușurează în multe privințe munca; de exemplu, demonstrația faptului că reuniunea limbajelor regulate este din nou un limbaj regulat se poate scrie cu ε-tranziții mult mai simplu decât în cazul automatelor finite deterministe. În această demonstrație aveam ca exemple aceste automate

și

iar apoi am construit un automat finit determinist care recunoștea reuniunea celor două limbaje. Cu ε-tranziții putem construi un astfel de automat în felul următor:

Pur și simplu adăugăm o nouă stare inițială, din ea pleacă două ε-tranziții spre stările inițiale ale automatelor originale și gata. Automatul decide nedeterminist dacă încearcă să accepte cuvântul cu unul sau cu celălalt „subautomat”.

Definiția automatului nedeterminist

Am arătat deja prin ce se deosebesc automatul finit determinist și cel nedeterminist, rămâne doar să formalizăm. Automatul finit determinist l-am definit ca un cvintuplu ⟨Q, Σ, δ, q₀, F⟩, unde Q este mulțimea stărilor, Σ este alfabetul, δ este funcția de tranziție, q₀ este starea inițială, iar F este mulțimea stărilor finale. Singurul lucru care se schimbă în definiția automatelor nedeterministe este definiția funcției de tranziție.

În varianta deterministă, funcția pentru apelul δ(q, w) putea returna o singură stare, în timp ce în varianta nedeterministă poate returna mai multe stări – dacă pentru un simbol sunt definite mai multe tranziții. Pentru că trebuie să definim și ε-tranzițiile, notăm mulțimea Σ ∪ {ε} cu Σ_ε, adică Σ_ε = Σ ∪ {ε}. Funcția δ o definim deci astfel:

$δ : Q \times Σ_{ε} \to 2^{Q}$

Notația 2^Q desemnează mulțimea părților, mulțimea tuturor submulțimilor mulțimii Q. Formalizarea calculului este foarte asemănătoare cu cea de la automatele finite. Configurația automatului este din nou perechea ⟨q, w⟩ ∈ Q × Σ^∗. Pasul de calcul ↦ este o relație pe mulțimea configurațiilor, astfel încât

$⟨ q_{i}, w_{0} w_{1} \dots w_{n} ⟩ \mapsto ⟨ q_{j}, w_{1} \dots w_{n} ⟩,$

dacă și numai dacă q_j ∈ δ(q_i, w₀). În această propoziție a fost cea mai mare diferență. La automatele deterministe aveam această condiție scrisă ca q_j = δ(q_i, w₀), pentru că funcția δ returna întotdeauna o singură stare. Versiunea nedeterministă a funcției de tranziție returnează o mulțime de stări, de aceea apare simbolul ∈. Închiderea reflexivă și tranzitivă a relației o vom nota din nou ↦ ^∗. Spunem că automatul acceptă cuvântul w dacă și numai dacă există q_f ∈ F astfel încât

$⟨ q_{0}, w ⟩ \mapsto^{*} ⟨ q_{f}, ε ⟩ .$

Surse

Capitole: Automat finit, Automat complet, Automat finit nedeterminist, Simularea AFN, Conversia AFN în AFD

« Anterior: Automat complet

Următor: Simularea AFN »