Regulære udtryk

Et regulært udtryk er en tekststreng, som gør det muligt at beskrive en mængde af ord. Regulære udtryk kan vi også opfatte som en enkel måde at beskrive en endelig automat på.

Hvad er et regulært udtryk

I aritmetik bruger vi symboler som · og + til at opstille et udtryk som for eksempel (2 + 3) · 4. Ved at beregne dette udtryk får vi et tal. Et regulært udtryk er en følge af tegn og nogle få specielle symboler, f.eks. a(x ∪ y), hvis værdi er et (formelt) sprog. Resultatet af udtrykket (2 + 3) · 4 er tallet 20, resultatet af det regulære udtryk a(x ∪ y) er mængden af to ord »ax«, »ay«.

Hvordan ville vi udregne det foregående regulære udtryk a(x ∪ y)? Hvert bogstav er i virkeligheden en forkortelse for en mængde med ét element, der indeholder det pågældende bogstav, og den skjulte multiplikation er konkatenering af ord. Det regulære udtryk kunne vi omskrive »i fuld længde« således:

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

Videre ville vi udregne det sådan: foreningen {x} ∪ {y} giver os sproget {x,y}. Ved at konkatenere sprogene {a} og {x,y} får vi sproget {ax, ay}.

Regulære udtryk bruges meget ofte i programmering, og de fleste programmeringssprog har regulære udtryk implementeret på en eller anden måde. Regulære udtryk bruges for eksempel til at kontrollere, om en tekst, brugeren har indtastet, opfylder bestemte kriterier (f.eks. om det er en gyldig e-mail, en gyldig dato osv.), og desuden til at erstatte tekster (vi kan for eksempel ville erstatte alle forekomster af URL i en tekst med links, der kan klikkes på osv.).

Virkelige implementeringer af regulære udtryk er for det meste stærkere end de regulære udtryk, der er beskrevet her, og bruger en lidt anderledes, men frem for alt mere kompliceret syntaks.

Definition af et regulært udtryk

Vi definerer et regulært udtryk over et alfabet Σ. Så siger vi, at et regulært udtryk er:

1. a, hvor a ∈ Σ. Dvs. et enkelt tegn i alfabetet er et regulært udtryk.
2. ϵ: det tomme ord, i programmering skrives det også som tomme anførselstegn »«.
3. ∅: et regulært udtryk skal også kunne beskrive det tomme sprog, så det tomme sprog er et regulært udtryk.
4. (R₁ ∪ R₂), hvor R₁, R₂ er regulære udtryk.
5. (R₁ ∘ R₂), hvor R₁, R₂ er regulære udtryk.
6. (R^∗), hvor R er et regulært udtryk.

I stedet for symbolet ∪ fra punkt 4 kan vi også bruge den lodrette streg: |. I stedet for symbolet ∘ behøver vi ikke bruge noget. Ligesom vi for det meste ikke skriver multiplikationstegnet, prikken ·, direkte, skriver vi for det meste heller ikke konkateneringstegnet ∘. Disse regulære udtryk er derfor identiske: a ∘ (b ∪ c) og a(b|c).

Hvad betyder de enkelte operatorer?

• ∪ eller | betegner forening af sprog.
• ∘ betegner konkatenering af sprog.
• ^∗ betegner Kleene-stjernen af et sprog.

Eksempler:

• a betegner det enkle sprog {a}.
• a|b betegner sproget bestående af de to ord {a, b}.
• a ∘ b betegner sproget {ab}.
• a(b|c)d betegner sproget {abd, acd}.
• a(b^∗) betegner sproget af alle ord, der begynder med bogstavet »a«, efterfulgt af et vilkårligt antal bogstaver »b«.
• (ab)^∗ betegner sproget af alle ord {ϵ, ab, abab, ababab, …}.
• 0^∗10^∗ betegner sproget af alle binære ord, der indeholder netop ét ettal. (Læg mærke til, at det ville være mere præcist at skrive dette udtryk sådan: (0^∗)1(0^∗), men når notationen er læselig også uden, kan vi udelade parenteserne.)
• Σ^∗1Σ^∗ betegner sproget af alle ord, der indeholder mindst ét ettal.
• (1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)^∗ betegner sproget af alle naturlige tal.

Videre viser vi ækvivalensen mellem regulære udtryk og endelige automater. Her gælder det, at der for hvert regulært udtryk, hvis værdi er sproget R, findes en endelig automat A, for hvilken der gælder L(A) = R, og omvendt.

Kilder

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