Säännölliset lausekkeet

Edellä esitellyissä KMP- ja AC-algoritmeissa sovellettiin äärellisiä automaatteja hahmontunnistukseen. Ilmeistä on, että äärelliset automaattit ovat tehokas apuväline hahmontunnistuksessa. Äärellisten automaattien kaikki mahdollisuudet tulevatkin hyödynnettyä vasta otettaessa hakukriteeriksi säännölliset lausekkeet. Säännöllisiä lausekkeita käytetään UNIX-käyttöjärjestelmästä peräisin olevissa tekstinmanipulointiohjelmissa (awk, sed, grep), yleiskäyttöisissä skripti-kielissä (perl, Tcl/Tk), sekä tekstitietokannoissa merkkijonojen hakukriteerinä. Säännöllisten lausekkeiden hyödyllisyys seuraa niiden hyvästä ilmaisuvoimasta, tehokkaista toteutusmahdollisuuksista, sekä vankasta teoriapohjasta.

Aakkoston $\Sigma$ säännölliset lausekkeet määritellään induktiivisesti seuraavilla säännöillä:

1. $\emptyset$ on säännöllinen lauseke (lauseke, joka ei hyväksy mitään merkkijonoa);
2. $\lambda$ on säännöllinen lauseke (lauseke, joka hyväksyy tyhjän merkkijonon);
3. $a$ on säännöllinen lauseke kaikilla $a \in \Sigma$;
4. jos $r$ ja $s$ ovat $\Sigma$:n säännöllisiä lausekkeita, niin $(r \cup s)$, $(rs)$ ja $r^*$ ovat $\Sigma$:n säännöllisiä lausekkeita;
5. muita $\Sigma$:n säännöllisiä lausekkeita ei ole.

Näin ollen säännöllisiä lausekkeita ovat mm.

• $(hahmontunnistus)$: merkkijonon ``hahmontunnistus'' tunnistava säännöllinen lauseke.
• $( he \cup she \cup his \cup hers )$: kuvan 2 hahmot tunnistava säännöllinen lauseke.
• $( 0 \cup 1 \cup 2 \cup 3 \cup 4 \cup 5 \cup 6 \cup 7 \cup 8 \cup 9 )^*$: kokonaisluvut tunnistava säännöllinen lauseke.

Säännöllisten lausekkeiden muuntaminen epädeterministiseksi tai deterministiseksi äärelliseksi automaatiksi ja automaatin simuloiminen on esitelty luentomonisteessa [Orp95].