✖

Reguliere expressies

Een reguliere expressie is een tekenreeks waarmee je een verzameling woorden kunt beschrijven. We kunnen reguliere expressies ook zien als een eenvoudige manier om een eindige automaat te beschrijven.

Wat is een reguliere expressie

In de rekenkunde gebruiken we symbolen als · en + om een uitdrukking te maken zoals (2 + 3) · 4. Door deze uitdrukking uit te rekenen krijgen we een getal. Een reguliere expressie is een rij tekens en een paar speciale symbolen, bijvoorbeeld a(x ∪ y), waarvan de waarde een (formele) taal is. De uitkomst van de uitdrukking (2 + 3) · 4 is het getal 20, de uitkomst van de reguliere expressie a(x ∪ y) is de verzameling van de twee woorden “ax”, “ay”.

Hoe zouden we de vorige reguliere expressie a(x ∪ y) uitwerken? Elke letter is in feite een afkorting voor een verzameling met één element, de gegeven letter, en het verborgen maalteken is concatenatie van woorden. We zouden de reguliere expressie “voluit” zo kunnen schrijven:

{a}∘({x}∪{y})

Verder zouden we haar zo uitwerken: de vereniging {x} ∪ {y} geeft ons de taal {x,y}. Door de talen {a} en {x,y} te concateneren krijgen we de taal {ax, ay}.

Reguliere expressies worden heel vaak gebruikt bij het programmeren en de meeste programmeertalen hebben reguliere expressies op de een of andere manier geïmplementeerd. Reguliere expressies worden bijvoorbeeld gebruikt om te controleren of een tekst die een gebruiker heeft ingevoerd aan bepaalde criteria voldoet (bijvoorbeeld of het een geldig e-mailadres is, een geldige datum enzovoort), en ook om teksten te vervangen (we willen bijvoorbeeld alle url's in een tekst vervangen door klikbare links).

Echte implementaties van reguliere expressies zijn meestal krachtiger dan de hier beschreven reguliere expressies en gebruiken een iets andere, maar vooral ingewikkeldere syntaxis.

Definitie van een reguliere expressie

We definiëren een reguliere expressie over een alfabet Σ. We zeggen dan dat een reguliere expressie is:

  1. a, waarbij a ∈ Σ. Een los teken van het alfabet is dus een reguliere expressie.
  2. ϵ: het lege woord, dat in de programmeerpraktijk ook wordt geschreven als lege aanhalingstekens “”.
  3. ∅: een reguliere expressie moet ook de lege taal kunnen beschrijven, dus de lege taal is een reguliere expressie.
  4. (R1 ∪ R2), waarbij R1, R2 reguliere expressies zijn.
  5. (R1 ∘ R2), waarbij R1, R2 reguliere expressies zijn.
  6. (R∗), waarbij R een reguliere expressie is.

In plaats van het symbool ∪ uit punt 4 kunnen we ook het symbool van de verticale streep gebruiken: |. In plaats van het symbool ∘ hoeven we niets te gebruiken. Net zoals we het maalteken, de halfhoge punt ·, meestal niet echt schrijven, schrijven we ook het concatenatiesymbool ∘ meestal niet. Deze reguliere expressies zijn dus identiek: a ∘ (b ∪ c) en a(b|c).

Wat betekenen de afzonderlijke operatoren?

  • ∪ of | geeft de vereniging van talen aan.
  • ∘ geeft de concatenatie van talen aan.
  • ∗ geeft de afsluiting van een taal aan.

Voorbeelden:

  • a geeft de eenvoudige taal {a} aan.
  • a|b geeft de taal aan die uit de twee woorden {a, b} bestaat.
  • a ∘ b geeft de taal {ab} aan.
  • a(b|c)d geeft de taal {abd, acd} aan.
  • a(b∗) geeft de taal aan van alle woorden die beginnen met de letter “a”, gevolgd door een willekeurig aantal letters “b”.
  • (ab)∗ geeft de taal aan van alle woorden {ϵ, ab, abab, ababab, …}.
  • 0∗10∗ geeft de taal aan van alle binaire woorden die precies één symbool 1 bevatten. (Merk op dat het preciezer zou zijn deze expressie zo te schrijven: (0∗)1(0∗), maar als de notatie ook zonder leesbaar is, kunnen we de haakjes weglaten.)
  • Σ∗1Σ∗ geeft de taal aan van alle woorden die minstens één symbool 1 bevatten.
  • (1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)∗ geeft de taal aan van alle natuurlijke getallen.

Vervolgens laten we de equivalentie zien tussen reguliere expressies en eindige automaten. Voor elke reguliere expressie waarvan de waarde een taal R is, bestaat een eindige automaat A waarvoor L(A) = R geldt, en omgekeerd.

Bronnen

Hoofdstukken: Reguliere expressies, Omzetting van een reguliere expressie naar een automaat, Gegeneraliseerde niet-deterministische eindige automaat, Omzetting van een automaat naar een reguliere expressie