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

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια

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

[Επεξεργασία] Ορισμός

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

[Επεξεργασία] Βιβλιογραφία

  • H.R. Lewis, C.H. Papadimitriou, Elements of the Theory of Computation, Prentice Hall, 2nd Edition
Άλλες γλώσσες