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

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

Ορισμός 

Κανονικές εκφράσεις επί του  ορίζονται ως όλες οι συμβολοσειρές (strings) επί του  που σχηματίζονται ακολούθως:
 Το κενό και κάθε στοιχείο του Σ είναι κανονική έκφραση.
 Αν  και  είναι κανονικές εκφράσεις τότε και η παράθεσή τους (concatenation), , είναι κανονική έκφραση.
 Αν  και  είναι κανονικές εκφράσεις τότε και η ένωσή τους (union), , είναι κανονική έκραση.
 Αν  είναι κανονική έκφραση τότε και η  είναι κανονική έκφραση.
 Καμία άλλη στοιχειοσειρά δεν είναι κανονική έκφραση εκτός αν ικανοποιεί τους κανόνες 1 εως 4.

όπου 
  το αλφάβητο,
  το σύνολο των συμβολοσειρών επί του αλφαβήτου .
  το κενό σύνολο,
  το αστέρι Κλέινι (Kleene Star),
  η πράξη της ένωσης.

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

Παραδείγματα 
Με αλφάβητο το  με την κανονική έκφραση  περιγράφονται όλες οι στοιχειοσειρές που περιέχουν την abba.

Με αλφάβητο το  με την κανονική έκφραση  περιγράφονται όλες οι γραμματοσειρές που σχηματίζονται με σύμβολα του  και έχουν μήκος 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.

Τυπικές γλώσσες
Δομές προγραμματισμού
Αντιπαραβολή προτύπων