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

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

Ορισμός

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

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

Βιβλιογραφία

• H.R. Lewis, C.H. Papadimitriou, Elements of the Theory of Computation, Prentice Hall, 2nd Edition

Εξωτερικοί σύνδεσμοι

• http://aetos.it.teithe.gr/~theochim/GlwssesKaiMetaglwttistes/theoria/KavovikesEkfraseis.pdf. Αρχειοθέτηση 05/03/2016.