Expresii regulate

O expresie regulată este un șir de caractere care permite descrierea unei mulțimi de cuvinte. Expresiile regulate le putem privi și ca pe un mod simplu de a descrie un automat finit.

Ce este o expresie regulată

În aritmetică folosim simboluri ca · și + pentru a alcătui o expresie, de exemplu (2 + 3) · 4. Evaluând această expresie obținem un număr. O expresie regulată este un șir de caractere și de câteva simboluri speciale, de exemplu a(x ∪ y), a cărei evaluare este un limbaj (formal). Rezultatul expresiei (2 + 3) · 4 este numărul 20, iar rezultatul expresiei regulate a(x ∪ y) este mulțimea a două cuvinte „ax”, „ay”.

Cum am evalua expresia regulată de mai sus, a(x ∪ y)? Fiecare literă este de fapt o prescurtare pentru o mulțime cu un singur element, care conține litera respectivă, iar înmulțirea subînțeleasă este concatenarea cuvintelor. Expresia regulată am putea-o rescrie „în forma completă” astfel:

$$\left\{a\right\}\circ (\left\{x\right\}\cup \left\{y\right\})$$

Am evalua-o apoi astfel: reuniunea {x} ∪ {y} ne dă limbajul {x,y}. Prin concatenarea limbajelor {a} și {x,y} obținem limbajul {ax, ay}.

Expresiile regulate sunt folosite foarte des în programare, iar majoritatea limbajelor de programare le implementează într-un fel sau altul. Expresiile regulate se folosesc, de exemplu, pentru a verifica dacă un text introdus de utilizator îndeplinește anumite criterii (de pildă, dacă este o adresă de email validă, o dată validă etc.), precum și pentru înlocuirea textelor (de exemplu, putem vrea să înlocuim toate URL-urile dintr-un text cu linkuri pe care se poate da clic).

Implementările reale ale expresiilor regulate sunt de obicei mai puternice decât expresiile regulate descrise aici și folosesc o sintaxă ușor diferită, dar mai ales mai complicată.

Definiția expresiei regulate

Vom defini expresia regulată peste un alfabet Σ. Spunem că o expresie regulată este:

1. a, unde a ∈ Σ. Adică un simbol al alfabetului este el însuși o expresie regulată.
2. ϵ: cuvântul vid; în programare se scrie și ca ghilimele goale „”.
3. ∅: o expresie regulată trebuie să poată descrie și limbajul vid, deci limbajul vid este o expresie regulată.
4. (R₁ ∪ R₂), unde R₁, R₂ sunt expresii regulate.
5. (R₁ ∘ R₂), unde R₁, R₂ sunt expresii regulate.
6. (R^∗), unde R este o expresie regulată.

În locul simbolului ∪ de la punctul 4 putem folosi și bara verticală: |. În locul simbolului ∘ nu e nevoie să folosim nimic. Asemenea modului în care, de obicei, nu scriem direct simbolul înmulțirii, punctul ·, de cele mai multe ori nu scriem nici simbolul concatenării ∘. Aceste expresii regulate sunt deci identice: a ∘ (b ∪ c) și a(b|c).

Ce înseamnă operatorii?

• ∪ sau | denotă reuniunea limbajelor.
• ∘ denotă concatenarea limbajelor.
• ^∗ denotă închiderea Kleene a limbajului.

Exemple:

• a denotă limbajul simplu {a}.
• a|b denotă limbajul format din două cuvinte, {a, b}.
• a ∘ b denotă limbajul {ab}.
• a(b|c)d denotă limbajul {abd, acd}.
• a(b^∗) denotă limbajul tuturor cuvintelor care încep cu litera „a”, urmată de un număr oarecare de litere „b”.
• (ab)^∗ denotă limbajul tuturor cuvintelor {ϵ, ab, abab, ababab, …}.
• 0^∗10^∗ denotă limbajul tuturor cuvintelor binare care conțin exact o unitate. (Observă că, mai exact, ar fi trebuit să scriem această expresie astfel: (0^∗)1(0^∗), dar, când scrierea este lizibilă și fără ele, putem omite parantezele.)
• Σ^∗1Σ^∗ denotă limbajul tuturor cuvintelor care conțin cel puțin o unitate.
• (1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)^∗ denotă limbajul tuturor numerelor naturale nenule.

În continuare vom arăta echivalența dintre expresiile regulate și automatele finite. Pentru fiecare expresie regulată a cărei evaluare este limbajul R există un automat finit A pentru care L(A) = R, și invers.

Surse

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