Säännölliset lausekkeet

Säännöllinen lauseke on merkkijono, jolla voi kuvata jonkin sanojen joukon. Säännöllisiä lausekkeita voi myös pitää yksinkertaisena tapana kuvata äärellinen automaatti.

Mikä säännöllinen lauseke on

Aritmetiikassa käytämme symboleja · ja + muodostaaksemme lausekkeen, esimerkiksi (2 + 3) · 4. Kun tämän lausekkeen arvo lasketaan, saadaan luku. Säännöllinen lauseke on jono merkkejä ja muutamia erityisiä symboleja, esimerkiksi a(x ∪ y), jonka arvo on (formaali) kieli. Lausekkeen (2 + 3) · 4 tulos on luku 20, säännöllisen lausekkeen a(x ∪ y) tulos on kahden sanan ”ax”, ”ay” joukko.

Miten laskisimme edellisen säännöllisen lausekkeen a(x ∪ y) arvon? Jokainen kirjain on oikeastaan lyhenne yksialkioiselle joukolle, joka sisältää kyseisen kirjaimen, ja piilotettu kertolasku on sanojen konkatenaatio. Säännöllisen lausekkeen voisi kirjoittaa ”kokonaisuudessaan” näin:

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

Laskisimme sen edelleen näin: yhdiste {x} ∪ {y} muodostaa kielen {x,y}. Kielten {a} ja {x,y} konkatenaatiolla saamme kielen {ax, ay}.

Säännöllisiä lausekkeita käytetään ohjelmoinnissa hyvin usein, ja useimmissa ohjelmointikielissä on säännölliset lausekkeet toteutettu jollakin tavalla. Säännöllisillä lausekkeilla tarkistetaan esimerkiksi, täyttääkö käyttäjän syöttämä teksti tietyt ehdot (esim. onko se kelvollinen sähköpostiosoite, kelvollinen päivämäärä jne.), ja niillä korvataan tekstiä (voimme esimerkiksi haluta korvata kaikki tekstissä olevat URL-osoitteet napsautettavilla linkeillä jne.).

Säännöllisten lausekkeiden todelliset toteutukset ovat yleensä tässä kuvattuja säännöllisiä lausekkeita tehokkaampia ja käyttävät hieman erilaista, mutta ennen kaikkea monimutkaisempaa syntaksia.

Säännöllisen lausekkeen määritelmä

Määrittelemme säännöllisen lausekkeen jonkin aakkoston Σ yllä. Sanomme silloin, että säännöllinen lauseke on:

1. a, jossa a ∈ Σ. Eli pelkkä aakkoston merkki on säännöllinen lauseke.
2. ϵ: tyhjä sana, jota ohjelmoinnissa merkitään myös tyhjillä lainausmerkeillä ””.
3. ∅: säännöllisen lausekkeen täytyy pystyä kuvaamaan myös tyhjä kieli, joten tyhjä kieli on säännöllinen lauseke.
4. (R₁ ∪ R₂), jossa R₁, R₂ ovat säännöllisiä lausekkeita.
5. (R₁ ∘ R₂), jossa R₁, R₂ ovat säännöllisiä lausekkeita.
6. (R^∗), jossa R on säännöllinen lauseke.

Kohdan 4 symbolin ∪ sijasta voimme käyttää myös pystyviivaa: |. Symbolin ∘ sijasta emme tarvitse mitään. Samoin kuin kertomerkkiä, keskipistettä ·, ei yleensä kirjoiteta suoraan näkyviin, emme yleensä kirjoita myöskään konkatenaation symbolia ∘. Nämä säännölliset lausekkeet ovat siis samat: a ∘ (b ∪ c) ja a(b|c).

Mitä yksittäiset operaattorit tarkoittavat?

• ∪ tai | tarkoittaa kielten yhdistettä.
• ∘ tarkoittaa kielten konkatenaatiota.
• ^∗ tarkoittaa kielen Kleenen tähteä.

Esimerkkejä:

• a tarkoittaa yksinkertaista kieltä {a}.
• a|b tarkoittaa kieltä, joka koostuu kahdesta sanasta {a, b}.
• a ∘ b tarkoittaa kieltä {ab}.
• a(b|c)d tarkoittaa kieltä {abd, acd}.
• a(b^∗) tarkoittaa kaikkien niiden sanojen kieltä, jotka alkavat kirjaimella ”a” ja sen jälkeen tulee mikä tahansa määrä kirjaimia ”b”.
• (ab)^∗ tarkoittaa kaikkien sanojen kieltä {ϵ, ab, abab, ababab, …}.
• 0^∗10^∗ tarkoittaa kaikkien sellaisten binäärisanojen kieltä, joissa on täsmälleen yksi ykkönen. (Huomaa, että tarkempaa olisi kirjoittaa tämä lauseke näin: (0^∗)1(0^∗), mutta kun merkintä on luettavissa ilman sitäkin, voimme jättää sulut pois.)
• Σ^∗1Σ^∗ tarkoittaa kaikkien sellaisten sanojen kieltä, joissa on ainakin yksi ykkönen.
• (1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)^∗ tarkoittaa kaikkien positiivisten kokonaislukujen kieltä.

Seuraavaksi näytämme, että säännölliset lausekkeet ja äärelliset automaatit ovat ekvivalentteja. Jokaiselle säännölliselle lausekkeelle, jonka arvo on kieli R, on olemassa äärellinen automaatti A, jolle pätee L(A) = R, ja päinvastoin.

Lähteet

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