Ohjeet

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.

Merkinnät

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 |()*+?{,}[-].

Vaihtoehdot

Pystyviiva tarkoittaa, että säännöllisen lausekkeen osat ovat vaihtoehtoisia. Esimerkiksi lauseke 00|111|0000 määrittelee merkkijonot 00, 111 ja 0000.

Sulut

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.

Toistot

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ät

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).

Teoriasta

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.