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

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Μετάβαση σε: πλοήγηση, αναζήτηση

Οι κανονικές έκφρασεις (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 = \{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

Εξωτερικοί σύνδεσμοι[Επεξεργασία | επεξεργασία κώδικα]