Conversia unui automat într-o expresie regulată

Vom arăta cum putem converti orice automat finit într-o expresie regulată.

Descrierea algoritmului

La intrare avem un AFN A. Mai întâi îl transformăm într-un AFNG. În a doua fază eliminăm de fiecare dată câte o stare, modificăm corespunzător funcția de tranziție și repetăm până când rămân doar două stări – cea inițială și cea finală. Între ele va exista o tranziție etichetată cu o expresie regulată, iar aceasta este rezultatul întregului algoritm. Tot procedeul constă, așadar, în eliminarea unei stări și în corectarea ulterioară a automatului, astfel încât să obținem un automat echivalent.

Eliminarea unei stări

Cum se elimină o stare, putem vedea pe un exemplu simplu. Presupunem că o parte din automatul nostru arată astfel:

unde R_i sunt niște expresii regulate. Cum ar arăta automatul dacă am elimina starea q_r? Ne putem imagina că ne aflăm în starea q_i și ne întrebăm ce cuvinte putem genera pe această porțiune. Dacă mergem direct din starea q_i în starea q_j, vom obține toate cuvintele care corespund expresiei regulate R₄.

Dacă însă mergem în starea q_r, putem genera cuvinte de forma R₁. În starea q_r putem rămâne în buclă, după expresia regulată R₂, deci putem genera de fapt cuvinte de forma $R_1\circ (R_2^{\ast })$. Și, pentru că din starea q_r mai putem trece în starea q_j, adăugăm la final expresia regulată R₃. În total, pe acest drum obținem cuvinte de forma $R_1\circ (R_2^{\ast })\circ R_3$.

Acum știm că din această parte a automatului pot rezulta cuvinte de forma R₄ sau de forma $R_1\circ (R_2^{\ast })\circ R_3$. Putem scrie aceasta, desigur, sub forma unei expresii regulate: $(R_4)|(R_1\circ (R_2^{\ast })\circ R_3)$.

Acum putem elimina simplu starea q_r și păstra doar cele două stări q_i și q_j, iar în locul lui R₄ scriem expresia tocmai obținută:

Acest procedeu îl aplicăm fiecărei tranziții din fiecare stare q_i într-o stare q_j, inclusiv buclelor, adică și cazului în care q_i = q_j.

După eliminarea unei stări obținem un automat echivalent – un automat care recunoaște același limbaj.

Algoritmul complet

La intrare avem un AFN A = ⟨Q, Σ, δ, q₀, F⟩.

1. Convertim AFN-ul A într-un AFNG Z = ⟨Q′, Σ, δ′, q₀′, q_f′⟩. În continuare notăm cu k numărul de stări din Z.
2. Dacă k = 2, algoritmul se oprește, iar pe tranziția dintre starea inițială și cea finală se află expresia regulată căutată.
3. Dacă k>2, alegem o stare oarecare q_r, diferită de starea inițială și de cea finală, adică q_r ≠ q₀′ și q_r ≠ q_f′. Apoi construim un nou AFNG Z′ = ⟨Q′′, Σ, δ′′,q₀′,q_f′⟩, pentru care are loc: $$Q^{\prime \prime }=Q^{\prime }\setminus \left\{q_r\right\}$$ și pentru toate q_i ∈ Q′′ ∖ {q_f′} și pentru toate q_j ∈ Q′′ ∖ {q₀′} fie $${\delta }^{\prime \prime }(q_i,q_j)=(R_4)|(R_1(R_2^{\ast })R_3),$$ unde R₁ = δ′(q_i,q_r), R₂ = δ′(q_r,q_r), R₃ = δ′(q_r, q_j), R₄ = δ′(q_i, q_j). Apoi continuă cu pasul 2.

Exemplu

Fie la intrare acest automat finit:

Mai întâi îl convertim în AFNG (tranzițiile inutile etichetate cu ∅ nu le vom desena):

Acum aplicăm a doua parte a algoritmului și eliminăm o stare. Începem cu starea q₂. Eliminăm starea q₂ și adăugăm o tranziție din starea q₁ în starea q_f. Această tranziție o etichetăm cu b(a|b)^∗, deoarece din starea q₁ ajungem în starea q₂ prin cuvinte de forma b, apoi putem rămâne în buclă pentru a|b, ceea ce ne dă (a|b)^∗, iar la final trecem în q_f printr-o ε-tranziție. Aici are loc b(a|b)^∗ϵ = b(a|b)^∗. Obținem automatul:

Ne rămâne de eliminat ultima stare, q₁. Adăugăm o tranziție din starea q_s în starea q_f. Cu ce o etichetăm? În starea q₁ ajungem printr-o ε-tranziție, pe care o putem omite direct. Apoi putem rămâne în buclă pentru a, deci obținem expresia regulată a^∗. Și, în sfârșit, prin tranziția următoare ajungem în q_f, așa că expresia o concatenăm cu b(a|b)^∗. Tranziția va fi deci etichetată cu expresia regulată a^∗ b(a|b)^∗.

Automatul are acum doar două stări, deci algoritmul se oprește. Pe tranziție se află expresia regulată căutată.

Surse

• Exemplul și descrierea algoritmului provin din M. Sipser: Introduction to the Theory of Computation