Κανονική έκφραση

Οι κανονικές εκφράσεις ή κανονικές παραστάσεις (regular expressions, regexp ή regex) χρησιμοποιούνται για την περιγραφή γλωσσών με απλά σύμβολα, το $\emptyset$ και συνδυασμούς που προκύπτουν με εφαρμογή ένωσης ( $\cup$ ), του αστεριού Κλέινι (Kleene Star) ( $^{*}$ ) ή και παρενθέσεων.

Ορισμός[Επεξεργασία | επεξεργασία κώδικα]

Κανονικές εκφράσεις επί του $\Sigma ^{*}$ ορίζονται ως όλες οι συμβολοσειρές (strings) επί του $\Sigma \ \cup \ \{(,\ ),\ ^{*},\ \emptyset \}$ που σχηματίζονται ακολούθως:

Το κενό και κάθε στοιχείο του Σ είναι κανονική έκφραση.
Αν $a$ και $b$ είναι κανονικές εκφράσεις τότε και η παράθεσή τους (concatenation), $ab$ , είναι κανονική έκφραση.
Αν $a$ και $b$ είναι κανονικές εκφράσεις τότε και η ένωσή τους (union), $a\cup b$ , είναι κανονική έκραση.
Αν $a$ είναι κανονική έκφραση τότε και η $a^{*}$ είναι κανονική έκφραση.
Καμία άλλη στοιχειοσειρά δεν είναι κανονική έκφραση εκτός αν ικανοποιεί τους κανόνες 1 εως 4.

όπου

$\Sigma$ το αλφάβητο,
$\Sigma ^{*}$ το σύνολο των συμβολοσειρών επί του αλφαβήτου $\Sigma$ .
$\emptyset$ το κενό σύνολο,
$^{*}$ το αστέρι Κλέινι (Kleene Star),
$\cup$ η πράξη της ένωσης.

Σε ορισμένα βιβλία η πράξη της ένωσης απαντάται και ως | ή + .

Παραδείγματα[Επεξεργασία | επεξεργασία κώδικα]

Με αλφάβητο το $\Sigma =\{a,\ b\}$ με την κανονική έκφραση $(a^{*}b^{*})^{*}(abba)\ (a^{*}b^{*})^{*}$ περιγράφονται όλες οι στοιχειοσειρές που περιέχουν την abba.

Με αλφάβητο το $\Sigma =\{a,\ b,\ c\}$ με την κανονική έκφραση $(a\cup b\cup c)\ (a\cup b\cup c)\ (a\cup b\cup c)$ περιγράφονται όλες οι γραμματοσειρές που σχηματίζονται με σύμβολα του $\Sigma$ και έχουν μήκος 3.