Κανονικές εκφράσεις

Μια κανονική έκφραση (regular expression) είναι ένας συμβολισμός κατάλληλος για την περιγραφή μιας κανονικής γλώσσας. Πολλά εργαλεία προγραμματισμού βασίζονται σε κανονικές εκφράσεις για την περιγραφή και την αναγνώριση συμβολοσειρών. Μπορούμε να ορίσουμε μια κανονική έκφραση σύμφωνα με τους παρακάτω κανόνες:

Για ένα σύμβολο της αλφαβήτου a η κανονική έκφραση a συμβολίζει τη γλώσσα {a}.
Αν R και S δύο κανονικές εκφράσεις για τις γλώσσες L_R και L_S τότε:
- η έκφραση R|S συμβολίζει τη γλώσσα L_R U L_S.
- η έκφραση R.S συμβολίζει τη γλώσσα L_R . L_S.
- η έκφραση R^* συμβολίζει τη γλώσσα L_R^*.
- η έκφραση R⁺ συμβολίζει τη γλώσσα L_R⁺.

Ο τελεστής * έχει την υψηλότερη και ο τελεστής | τη χαμηλότερη προτεραιότητα.