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

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

Ορισμός

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

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

όπου

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

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

Παραδείγματα

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

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