Simularea unui automat nedeterminist

Dacă avem un automat nedeterminist și vrem să aflăm dacă acceptă un anumit cuvânt, putem converti automatul într-unul determinist, putem încerca cumva să-l verificăm sau putem folosi un algoritm care simulează funcționarea AFN-ului.

Principiul algoritmului

Vom arăta principiul pe un exemplu potrivit. Fie acest automat:

Este un automat finit nedeterminist care acceptă un anumit limbaj. Acum nu ne interesează deloc care anume. Vom vedea cum poate arăta calculul unui astfel de automat pentru cuvântul de intrare 11001. Raționamentul este următorul: prelucrăm un simbol din cuvânt și ne uităm în ce stări putem ajunge datorită tranzițiilor multiple pentru același simbol. Reținem toate aceste stări și, în pasul următor, presupunem că ne aflăm „în toate aceste stări simultan” și ne interesează unde putem ajunge mai departe din ele.

Vom reține astfel mulțimea stărilor în care ne putem afla și partea necitită a cuvântului. La început avem perechea ⟨{q₀}, 11001⟩. Pornim din starea q₀ (starea inițială), iar la intrare avem cuvântul 11001. Automatul arată astfel; cu roșu și îngroșat este evidențiată starea în care ne aflăm:

Primul simbol este 1, iar din starea q₀ pleacă o singură tranziție pentru simbolul 1, deci ajungem în starea q₁. Reținem perechea ⟨{q₁}, 1001⟩. Automatul arată astfel:

Continuăm. Partea necitită a cuvântului este 1001, deci căutăm din nou tranzițiile pentru 1. Acum sunt două – înapoi în starea q₀ și mai departe în starea q₃. Ne îndreptăm acum în ambele stări deodată. Reținem astfel perechea ⟨{q₀, q₃}, 001⟩.

Care este logica? Știm că există un drum prin care, cu cuvântul 11, ajungem din starea inițială atât în starea q₃, cât și în starea q₀. Încă nu știm care ramură ne va fi utilă, așa că le reținem pe amândouă. Continuăm. La intrare avem simbolul 0. Acum trebuie să ne uităm atât la tranzițiile din q₀, cât și la cele din q₃. Din starea q₀ pleacă tranziții spre stările q₁ și q₂, iar din starea q₃ pleacă o tranziție înapoi spre q₁. Luăm în calcul toate aceste stări și obținem perechea ⟨{q₁, q₂}, 01⟩:

Dar încă nu am terminat acest pas. Vedem că din starea q₂ pleacă o ε-tranziție spre starea q₄. Știm că putem trece printr-o ε-tranziție „oricând”, fără să citim un alt simbol. Cu alte cuvinte, fără să citim următorul simbol din cuvântul de intrare, ne mai putem muta în starea q₄. Adăugăm astfel starea q₄ la stările în care ne putem afla: ⟨{q₁, q₂, q₄}, 01⟩. Am colora automatul astfel:

Mai departe, la intrare este 0. Ne uităm unde ne putem muta din cele trei stări în care ne aflăm. Din q₁ nu ne putem muta nicăieri, deoarece lipsește tranziția pentru 0. Calculul pe această ramură se oprește. Nici din starea q₄ nu ajungem nicăieri. Din starea q₂ ajungem înapoi în starea q₂. Dar, cum din starea q₂ pleacă din nou o ε-tranziție spre starea q₄, putem ajunge și în starea q₄. Din mulțimea de stări {q₁, q₂, q₄} putem ajunge astfel, pentru simbolul 0, în mulțimea de stări {q₂, q₄} și obținem perechea ⟨{q₂, q₄}, 1⟩:

La final avem la intrare simbolul 1. Din starea q₂ nu ajungem nicăieri, iar calculul pe această ramură se oprește. Din starea q₄ însă ajungem în stările q₃ și q₅. Obținem perechea ⟨{q₃, q₅}, ε⟩:

Automatul a citit acum tot cuvântul și „se află” în două stări: q₃, q₅. Deoarece cel puțin una dintre ele este stare finală, automatul acceptă cuvântul 11001.

Algoritmul

Mai întâi avem nevoie de o funcție care primește ca parametru o mulțime de stări și calculează în ce alte stări mai putem ajunge prin ε-tranziții. Intrarea este automatul ⟨Q, Σ, δ, q₀, F⟩ și mulțimea de stări States, iar ieșirea este o supermulțime a acestor stări, formată din stările în care se poate ajunge prin ε-tranziții. Această operație o vom numi ε-închiderea mulțimii States.

$\begin{aligned} Function E p s i l o n C l o s u r e (⟨ Q, Σ, δ, q_{0}, F ⟩, S t a t e s) \\ N e x t S t a t e s \leftarrow \emptyset \\ ForEach q \in S t a t e s Do \\ N e x t S t a t e s \leftarrow N e x t S t a t e s \cup {q} \cup δ (q, ε) \\ EndFor \\ If N e x t S t a t e s ∖ S t a t e s = \emptyset Do \\ Return S t a t e s \\ Else \\ Return E p s i l o n C l o s u r e (⟨ Q, Σ, δ, q_{0}, F ⟩, N e x t S t a t e s) \\ EndIf \\ EndFunction \end{aligned}$

Această funcție o folosim în funcția care va simula funcționarea automatului nedeterminist. Intrarea este automatul, cuvântul de intrare w = w₁w₂… w_n și mulțimea de stări în care se află automatul în acel moment. Ieșirea este răspunsul Da sau Nu, după cum automatul acceptă sau nu cuvântul dat.

$\begin{aligned} Function C o m p u t e N F A (⟨ Q, Σ, δ, q_{0}, F ⟩, w, S t a t e s) \\ If w = ϵ Do \\ If S t a t e s \cap F \neq \emptyset Do \\ Return YES \\ Else \\ Return NO \\ EndIf \\ EndIf \\ N e x t S t a t e s \leftarrow \emptyset \\ ForEach q \in S t a t e s Do \\ N e x t S t a t e s \leftarrow N e x t S t a t e s \cup δ (q, w_{1}) \\ EndFor \\ N e x t S t a t e s \leftarrow E p s i l o n C l o s u r e (⟨ Q, Σ, δ, q_{0}, F ⟩, N e x t S t a t e s) \\ Return C o m p u t e N F A (⟨ Q, Σ, δ, q_{0}, F ⟩, w_{2} w_{3} \dots w_{n}, N e x t S t a t e s) \\ EndFunction \end{aligned}$

Dacă vrem să verificăm dacă automatul acceptă cuvântul w, apelăm funcția astfel: ComputeNFA(⟨Q, Σ, δ, q₀, F⟩, w, EpsilonClosure(⟨Q, Σ, δ, q₀, F⟩, {q₀})).

Surse

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

« Anterior: Automat finit nedeterminist

Următor: Conversia AFN în AFD »