Reguláris kifejezések

A reguláris kifejezés olyan szöveges karakterlánc, amellyel szavak valamilyen halmazát írhatjuk le. A reguláris kifejezéseket úgy is felfoghatjuk, mint a véges automata leírásának egyszerű módját.

Mi az a reguláris kifejezés

Az aritmetikában az olyan szimbólumokat, mint a · és a +, kifejezések összeállítására használjuk, például (2 + 3) · 4. A kifejezés kiértékelésével egy számot kapunk. A reguláris kifejezés karakterek és néhány speciális szimbólum sorozata, például a(x ∪ y), amelynek kiértékelése egy (formális) nyelv. A (2 + 3) · 4 kifejezés eredménye a 20 szám, az a(x ∪ y) reguláris kifejezés eredménye pedig két szó halmaza: „ax”, „ay”.

Hogyan értékelnénk ki az előző a(x ∪ y) reguláris kifejezést? Minden betű valójában az adott betűt tartalmazó egyelemű halmaz rövidítése, a rejtett szorzás pedig a szavak összefűzése. A reguláris kifejezést „teljes terjedelmében” így írhatnánk át:

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

Ezt aztán így értékelnénk ki: az {x} ∪ {y} unió létrehozza az {x,y} nyelvet. Az {a} és {x,y} nyelv összefűzésével megkapjuk az {ax, ay} nyelvet.

A reguláris kifejezéseket nagyon gyakran használják a programozásban, és a legtöbb programozási nyelvben valamilyen módon implementálva vannak. A reguláris kifejezésekkel ellenőrizhetjük például, hogy a felhasználó által megadott szöveg megfelel-e bizonyos feltételeknek (például hogy érvényes e-mail-cím vagy érvényes dátum-e), továbbá szövegek cseréjére is használják (például egy szövegben az összes URL-t kattintható hivatkozásra akarhatjuk cserélni).

A reguláris kifejezések valódi implementációi többnyire erősebbek az itt leírt reguláris kifejezéseknél, és kissé eltérő, de főleg bonyolultabb szintaxist használnak.

A reguláris kifejezés definíciója

A reguláris kifejezést valamilyen Σ ábécé felett definiáljuk. Azt mondjuk, hogy a reguláris kifejezés:

1. a, ahol a ∈ Σ. Vagyis az ábécé egy karaktere önmagában is reguláris kifejezés.
2. ϵ: az üres szó, a programozásban üres idézőjelként is írják: „”.
3. ∅: a reguláris kifejezésnek az üres nyelvet is le kell tudnia írni, ezért az üres nyelv is reguláris kifejezés.
4. (R₁ ∪ R₂), ahol R₁, R₂ reguláris kifejezések.
5. (R₁ ∘ R₂), ahol R₁, R₂ reguláris kifejezések.
6. (R^∗), ahol R reguláris kifejezés.

A 4. pontban az ∪ szimbólum helyett függőleges vonalat is használhatunk: |. A ∘ szimbólum helyett nem kell semmit használnunk. Ahogyan a szorzás jelét, a · szorzópontot többnyire nem írjuk ki, úgy az összefűzés ∘ jelét is többnyire nem írjuk ki. Ezek a reguláris kifejezések tehát azonosak: a ∘ (b ∪ c) és a(b|c).

Mit jelentenek az egyes operátorok?

• ∪ vagy | a nyelvek unióját jelöli.
• ∘ a nyelvek összefűzését jelöli.
• ^∗ a nyelv lezárását jelöli.

Példák:

• a az egyszerű {a} nyelvet jelöli.
• a|b a két szóból álló {a, b} nyelvet jelöli.
• a ∘ b az {ab} nyelvet jelöli.
• a(b|c)d az {abd, acd} nyelvet jelöli.
• a(b^∗) azoknak a szavaknak a nyelvét jelöli, amelyek „a” betűvel kezdődnek, és utána tetszőleges számú „b” betű következik.
• (ab)^∗ az összes {ϵ, ab, abab, ababab, …} szó nyelvét jelöli.
• 0^∗10^∗ azoknak a bináris szavaknak a nyelvét jelöli, amelyek pontosan egy egyest tartalmaznak. (Figyeld meg, hogy pontosabb lenne ezt a kifejezést így írni: (0^∗)1(0^∗), de ha a jelölés zárójelek nélkül is olvasható, elhagyhatjuk őket.)
• Σ^∗1Σ^∗ azoknak a szavaknak a nyelvét jelöli, amelyek legalább egy egyest tartalmaznak.
• (1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)^∗ az összes pozitív egész szám nyelvét jelöli.

A továbbiakban megmutatjuk az egyenértékűséget a reguláris kifejezések és a véges automaták között. Eszerint minden olyan reguláris kifejezéshez, amelynek kiértékelése az R nyelv, létezik olyan A véges automata, amelyre L(A) = R, és fordítva.

Források

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