Reguljära uttryck

Ett reguljärt uttryck är en textsträng som gör det möjligt att beskriva en mängd ord. Reguljära uttryck kan också ses som ett enkelt sätt att beskriva en ändlig automat.

Vad är ett reguljärt uttryck

I aritmetiken använder vi symboler som · och + för att bilda ett uttryck som till exempel (2 + 3) · 4. När vi beräknar uttrycket får vi ett tal. Ett reguljärt uttryck är en följd av tecken och några särskilda symboler, t.ex. a(x ∪ y), och när vi evaluerar det får vi ett (formellt) språk. Resultatet av uttrycket (2 + 3) · 4 är talet 20, och resultatet av det reguljära uttrycket a(x ∪ y) är mängden av de två orden ”ax”, ”ay”.

Hur skulle vi evaluera det reguljära uttrycket a(x ∪ y) ovan? Varje bokstav är egentligen en förkortning för en enelementsmängd som innehåller bokstaven, och den dolda multiplikationen är konkatenering av ord. Det reguljära uttrycket kan vi skriva om ”i full längd” så här:

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

Sedan skulle vi evaluera det så här: unionen {x} ∪ {y} ger oss språket {x,y}. Genom att konkatenera språken {a} och {x,y} får vi språket {ax, ay}.

Reguljära uttryck används mycket ofta i programmering, och de flesta programmeringsspråk har reguljära uttryck implementerade på något sätt. Reguljära uttryck används till exempel för att kontrollera om en text som användaren har skrivit in uppfyller vissa kriterier (t.ex. om det är en giltig e-postadress, ett giltigt datum osv.) och för att ersätta texter (vi kan till exempel vilja ersätta alla förekomster av en URL i en text med klickbara länkar osv.).

Verkliga implementeringar av reguljära uttryck är oftast kraftfullare än de reguljära uttryck som beskrivs här och använder en något annorlunda, men framför allt mer komplicerad syntax.

Definition av reguljära uttryck

Vi definierar reguljära uttryck över ett alfabet Σ. Då säger vi att ett reguljärt uttryck är:

1. a, där a ∈ Σ. Det vill säga, ett enskilt tecken i alfabetet är ett reguljärt uttryck.
2. ϵ: det tomma ordet, som i programmering också skrivs som tomma citattecken ””.
3. ∅: ett reguljärt uttryck måste också kunna beskriva det tomma språket, så det tomma språket är ett reguljärt uttryck.
4. (R₁ ∪ R₂), där R₁, R₂ är reguljära uttryck.
5. (R₁ ∘ R₂), där R₁, R₂ är reguljära uttryck.
6. (R^∗), där R är ett reguljärt uttryck.

I stället för symbolen ∪ i punkt 4 kan vi också använda det lodräta strecket: |. I stället för symbolen ∘ behöver vi inte använda något alls. På samma sätt som vi oftast inte skriver ut multiplikationstecknet, den mittställda punkten ·, skriver vi oftast inte heller ut konkateneringstecknet ∘. De här reguljära uttrycken är alltså identiska: a ∘ (b ∪ c) och a(b|c).

Vad betyder de olika operatorerna?

• ∪ eller | betecknar union av språk.
• ∘ betecknar konkatenering av språk.
• ^∗ betecknar Kleenestjärnan av ett språk.

Exempel:

• a betecknar det enkla språket {a}.
• a|b betecknar språket som består av de två orden {a, b}.
• a ∘ b betecknar språket {ab}.
• a(b|c)d betecknar språket {abd, acd}.
• a(b^∗) betecknar språket av alla ord som börjar med bokstaven ”a”, följd av ett godtyckligt antal bokstäver ”b”.
• (ab)^∗ betecknar språket av alla ord {ϵ, ab, abab, ababab, …}.
• 0^∗10^∗ betecknar språket av alla binära ord som innehåller exakt en etta. (Lägg märke till att det vore mer exakt att skriva uttrycket så här: (0^∗)1(0^∗), men när notationen är läsbar även utan det kan vi utelämna parenteserna.)
• Σ^∗1Σ^∗ betecknar språket av alla ord som innehåller minst en etta.
• (1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)^∗ betecknar språket av alla positiva heltal.

Härnäst visar vi att reguljära uttryck och ändliga automater är ekvivalenta. För varje reguljärt uttryck som evalueras till språket R finns det alltså en ändlig automat A för vilken L(A) = R, och tvärtom.

Källor

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