Säännöllinen lauseke määrittelee
joukon merkkijonoja.
Esimerkiksi säännöllinen lauseke
(11|111)0*
määrittelee merkkijonot,
joissa on alussa kaksi tai kolme
ykköstä ja sitten
mikä tahansa määrä nollia.
Säännölliset lausekkeet saivat alkunsa
tietojenkäsittelyn teorian tutkimuksesta,
mutta niille on myös paljon sovelluksia
ohjelmoinnissa ja tekstinkäsittelyssä.
SL-haaste sisältää joukon tehtäviä, joissa on tarkoituksena suunnitella säännöllisiä lausekkeita. Tehtävät on järjestetty niiden arvioidun vaikeuden mukaan: ensimmäiset tehtävät tutustuttavat säännöllisten lausekkeiden perusasioihin, kun taas viimeiset tehtävät ovat todellisia haasteita myös säännölliset lausekkeet hyvin tunteville.
SL-haasteen tekijät ovat Antti Laaksonen ja Lauri Kenttä. Palautetta ja ehdotuksia voi lähettää sähköpostitse.
Kaikissa tehtävissä
merkkijonot muodostuvat
numeromerkeistä
0...9.
Säännöllisen lausekkeen
suurin sallittu pituus
on 500 merkkiä,
mutta kaikkiin tehtäviin on
olemassa lauseke,
jonka pituus on alle 150 merkkiä.
Seuraavassa selostetaan merkinnät,
joita lausekkeissa voi käyttää.
Lyhyesti sanoen
sallitut merkinnät ovat
|()*+?{,}[-].
Pystyviiva tarkoittaa,
että säännöllisen lausekkeen osat
ovat vaihtoehtoisia.
Esimerkiksi lauseke
00|111|0000
määrittelee merkkijonot
00,
111 ja
0000.
Sulkujen avulla voi määrittää,
mihin säännöllisen lausekkeen
osaan muut merkinnät vaikuttavat.
Esimerkiksi lauseke
00(0|1)
määrittelee merkkijonot
000 ja 001.
Käytössä ovat seuraavat toistomerkinnät:
* |
toisto 0... kertaa |
+ |
toisto 1... kertaa |
? |
toisto 0 tai 1 kertaa |
{a} |
toisto a kertaa |
{a,b} |
toisto a...b kertaa |
{a,} |
toisto a... kertaa |
Esimerkiksi lauseke
(01)*
määrittelee tyhjän merkkijonon
sekä merkkijonot
01,
0101,
010101,
01010101, jne.
Vastaavasti lauseke
110?110?
määrittelee merkkijonot
1111,
11011,
11110 ja
110110.
Jos toistomerkintöjä on peräkkäin,
sisempien ympärillä täytyy käyttää sulkuja:
merkintä 0{2}* ei kelpaa,
mutta merkintä (0{2})* kelpaa.
Merkkiryhmän avulla voi määritellä lyhyesti joukon merkkejä.
Merkit kirjoitetaan hakasulkujen sisään,
ja merkkivälin voi määrittää viivan avulla.
Esimerkiksi merkintä
[145]
tarkoittaa samaa kuin
(1|4|5)
ja merkintä
[2-46-9]
tarkoittaa samaa kuin
(2|3|4|6|7|8|9).
SL-haasteen säännölliset lausekkeet vastaavat perinteisiä tietojenkäsittelyn teorian säännöllisiä lausekkeita. Sovelluksissa esiintyy kuitenkin usein laajennettuja säännöllisiä lausekkeita, jotka voivat määritellä sellaisia merkkijonojen joukkoja, joita perinteiset säännölliset lausekkeet eivät pysty määrittelemään.
Tyypillinen
laajennettujen säännöllisten
lausekkeiden ominaisuus on
takaisinviittaus (backreference).
Esimerkiksi lauseke
([01]*)\1
määrittelee merkkijonot,
joissa toistuu kahdesti sama
nollista ja ykkösistä
muodostuva osa
(kuten 0101 ja
11011101).
Voidaan kuitenkin osoittaa,
että tätä merkkijonojen joukkoa
on mahdotonta määritellä
perinteisillä
säännöllisillä lausekkeilla.
Perinteisten säännöllisten lausekkeiden teoria tunnetaan hyvin. SL-haasteen kannalta tärkeää on, että kahden säännöllisen lausekkeen vastaavuus voidaan tarkastaa täydellisesti. Teoriasta tiedetään myös seuraavat ominaisuudet:
Esimerkiksi lausekkeen
1(0|1)+
komplementti on lauseke
0(0|1)*|1?
(kun käytössä ovat merkit
0 ja 1).
Vastaavasti
lausekkeiden
([01][01])*
ja
10*
yhdiste on lauseke
([01][01])*|10*
ja leikkaus on lauseke
10(00)*.
Yhdistettä vastaavan lausekkeen muodostaminen on helppoa, koska riittää yhdistää alkuperäiset lausekkeet pystyviivan avulla. Komplementtia ja leikkausta vastaavien lausekkeiden muodostaminen on kuitenkin usein vaikeaa, mikä tulee esille monessa SL-haasteen tehtävässä.
Lyhimmän säännöllisen lausekkeen etsiminen on laskennallisesti vaikea ongelma. Yleisessä tapauksessa ongelma vastaa vaikeudeltaan PSPACE-täydellisen päätösongelman ratkaisemista, ja käytännössä ihminen vaikuttaa olevan usein tietokonetta parempi säännöllisten lausekkeiden suunnittelussa.
Säännöllisiä lausekkeita lähellä ovat myös äärelliset automaatit, joihin perehtymisestä voi olla hyötyä lausekkeiden suunnittelussa.