Conversia unei expresii regulate în automat

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

Exemplu

Înainte de a descrie algoritmul propriu-zis, vedem pe un exemplu despre ce este vorba. Fie această expresie regulată: a(b|c)x^∗. Limbajul generat de expresia regulată l-am descrie în cuvinte astfel: cuvinte care încep cu litera „a”, urmată fie de litera „b”, fie de „c”, iar apoi de un număr oarecare de litere „x”. Am putea construi un automat care să accepte acest limbaj? Sigur că da, uite:

Este clar că acest automat acceptă același limbaj. Se pune astfel întrebarea dacă pentru orice expresie regulată există un automat care acceptă limbajul respectiv. Ei bine, da.

Descrierea algoritmului de conversie a expresiei regulate în automat

Presupunem că la intrare avem o expresie regulată R. Din partea anterioară despre expresiile regulate știm că o expresie regulată poate avea în total șase forme diferite. Distingem deci șase cazuri:

1. R = a pentru un simbol a ∈ Σ. Adică expresia regulată este doar un singur simbol din alfabetul Σ peste care lucrăm. Automatul care ar accepta un singur simbol a ar arăta astfel:

   

2. R = ϵ, cuvântul vid. Automatul care ar accepta cuvântul vid ar arăta astfel:

   

3. R = ∅, expresia regulată care generează limbajul vid. Automatul care ar recunoaște un astfel de limbaj este acesta:

   

4. R = R₁ ∪ R₂, unde R₁, R₂ sunt expresii regulate. Știm deja că reuniunea limbajelor regulate este tot un limbaj regulat și că putem construi un automat care acceptă un astfel de limbaj. Cu alte cuvinte, presupunem că avem automatele care recunosc limbajele generate de expresiile R₁ și R₂ și cu ajutorul lor construim automatul care acceptă limbajul generat de expresia R₁ ∪ R₂. Exemplu: dacă R₁ = a și R₂ = ϵ, atunci, după procedeul descris, obținem acest automat:

   

5. R = R₁ ∘ R₂, unde R₁, R₂ sunt expresii regulate. Același caz ca la punctul precedent. Concatenarea limbajelor regulate este un limbaj regulat și putem construi astfel un automat care va accepta un astfel de limbaj. Deci, dacă R₁ = a, R₂ = b, concatenarea ar arăta astfel:

   

6. $R=(R_1^{\ast })$, unde R₁ este o expresie regulată. Din nou știm că închiderea Kleene a unui limbaj regulat este un limbaj regulat. Deci, dacă R = a^∗, automatul ar arăta astfel:

   

Aplicând succesiv aceste puncte, convertim întreaga expresie regulată într-un automat finit.

Exemplu complet

Încercăm să convertim expresia regulată (a|bc)^∗. Obținem pe rând aceste automate:

Acest automat final acceptă limbajul generat de expresia regulată (a|bc)^∗. Desigur, automatul este înspăimântător de complicat și există cu siguranță un automat mult mai simplu care acceptă același limbaj. Putem folosi algoritmul de conversie a AFN în AFD și apoi minimizarea automatului.

Surse

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