✖

Regulære uttrykk

Et regulært uttrykk er en tekststreng som gjør det mulig å beskrive en mengde ord. Regulære uttrykk kan vi også oppfatte som en enkel måte å beskrive en endelig automat på.

Hva et regulært uttrykk er

I aritmetikken bruker vi symboler som · og + til å bygge opp et uttrykk som for eksempel (2 + 3) · 4. Når vi regner ut dette uttrykket, får vi et tall. Et regulært uttrykk er en følge av tegn og noen få spesielle symboler, for eksempel a(x ∪ y), og resultatet av å regne det ut er et (formelt) språk. Resultatet av uttrykket (2 + 3) · 4 er tallet 20, og resultatet av det regulære uttrykket a(x ∪ y) er mengden av de to ordene «ax», «ay».

Hvordan ville vi regnet ut det forrige regulære uttrykket a(x ∪ y)? Hver bokstav er egentlig en forkortelse for en mengde med ett element som inneholder den bokstaven, og den skjulte multiplikasjonen er konkatenering av ord. Det regulære uttrykket kunne vi skrevet om «i full ordlyd» slik:

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

Videre ville vi regnet det ut slik: unionen {x} ∪ {y} gir oss språket {x,y}. Ved å konkatenere språkene {a} og {x,y} får vi språket {ax, ay}.

Regulære uttrykk brukes veldig ofte i programmering, og de fleste programmeringsspråk har regulære uttrykk implementert på en eller annen måte. Regulære uttrykk brukes for eksempel til å sjekke om en tekst brukeren har skrevet inn, oppfyller visse kriterier (for eksempel om den er en gyldig e-postadresse, en gyldig dato osv.), og til å erstatte tekster (for eksempel kan vi ønske å erstatte alle forekomster av URL-er i en tekst med klikkbare lenker osv.).

Virkelige implementeringer av regulære uttrykk er som regel kraftigere enn regulære uttrykk slik de er beskrevet her, og de bruker en litt annerledes, men framfor alt mer komplisert syntaks.

Definisjon av regulært uttrykk

Vi definerer regulære uttrykk over et alfabet Σ. Da sier vi at et regulært uttrykk er:

  1. a, der a ∈ Σ. Altså er et enkelt tegn i alfabetet et regulært uttrykk.
  2. ϵ: det tomme ordet, som i programmering også skrives som tomme anførselstegn «».
  3. ∅: et regulært uttrykk må også kunne beskrive det tomme språket, så det tomme språket er et regulært uttrykk.
  4. (R1 ∪ R2), der R1, R2 er regulære uttrykk.
  5. (R1 ∘ R2), der R1, R2 er regulære uttrykk.
  6. (R∗), der R er et regulært uttrykk.

I stedet for symbolet ∪ i punkt 4 kan vi også bruke symbolet loddrett strek: |. I stedet for symbolet ∘ trenger vi ikke bruke noe. På samme måte som vi som regel ikke skriver multiplikasjonstegnet, den midtstilte prikken ·, skriver vi som regel heller ikke symbolet for konkatenering ∘. Disse regulære uttrykkene er derfor identiske: a ∘ (b ∪ c) og a(b|c).

Hva betyr de enkelte operatorene?

  • ∪ eller | betegner union av språk.
  • ∘ betegner konkatenering av språk.
  • ∗ betegner Kleene-stjernen til et språk.

Eksempler:

  • a betegner det enkle språket {a}.
  • a|b betegner språket som består av de to ordene {a, b}.
  • a ∘ b betegner språket {ab}.
  • a(b|c)d betegner språket {abd, acd}.
  • a(b∗) betegner språket av alle ord som begynner med bokstaven «a», etterfulgt av et vilkårlig antall bokstaver «b».
  • (ab)∗ betegner språket av alle ordene {ϵ, ab, abab, ababab, …}.
  • 0∗10∗ betegner språket av alle binære ord som inneholder akkurat én ener. (Legg merke til at det ville vært mer nøyaktig å skrive dette uttrykket slik: (0∗)1(0∗), men når skrivemåten er leselig også uten det, kan vi utelate parentesene.)
  • Σ∗1Σ∗ betegner språket av alle ord som inneholder minst én ener.
  • (1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)∗ betegner språket av alle naturlige tall.

Videre skal vi vise ekvivalensen mellom regulære uttrykk og endelige automater. Her gjelder det at for hvert regulært uttrykk der resultatet er språket R, finnes det en endelig automat A som oppfyller L(A) = R, og omvendt.

Kilder

Kapitler: Regulære uttrykk, Omforming av regulært uttrykk til automat, Generalisert ikke-deterministisk endelig automat, Omforming av automat til regulært uttrykk