Κανονική έκφραση
Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Οι κανονικές έκφρασεις (regular expressions, regexp ή regex) χρησιμοποιούνται για την περιγραφή γλωσσών με απλά σύμβολα, το και συνδυασμούς που προκύπτουν με εφαρμογή ένωσης (
), του αστεριού Κλήνυ (Kleene Star) ( * ) ή και παρενθέσεων.
[Επεξεργασία] Ορισμός
Κανονικές εκφράσεις επί του Σ * ορίζονται ως όλες οι συμβολοσειρές (strings) επί του που σχηματίζονται ακολούθως:
- Το κενό και κάθε στοιχείο του Σ είναι κανονική έκφραση.
- Αν a και b είναι κανονικές εκφράσεις τότε και η συναλύσωσή τους (concatenation), ab, είναι κανονική έκφραση.
- Αν a και b είναι κανονικές εκφράσεις τότε και η ένωσή τους (union),
, είναι κανονική έκραση.
- Αν a είναι κανονική έκφραση τότε και η a * είναι κανονική έκφραση.
- Καμία άλλη στοιχειοσειρά δεν είναι κανονική έκφραση εκτός αν ικανοποιεί τους κανόνες 1 εως 4.
όπου
- Σ το αλφάβητο,
- Σ * το σύνολο των συμβολοσειρών επί του αλφαβήτου Σ.
το κενό σύνολο,
- * το αστέρι Κλήνυ (Kleene Star),
η πράξη της ένωσης.
Σε ορισμένα βιβλία η πράξη της ένωσης απαντάται και ως | ή + .
[Επεξεργασία] Παραδείγματα
Με αλφάβητο το με την κανονική έκφραση
περιγράφονται όλες οι στοιχειοσειρές που περιέχουν την abba.
Με αλφάβητο το με την κανονική έκφραση
περιγράφονται όλες οι γραμματοσειρές που σχηματίζονται με σύμβολα του Σ και έχουν μήκος 3.
[Επεξεργασία] Βιβλιογραφία
- H.R. Lewis, C.H. Papadimitriou, Elements of the Theory of Computation, Prentice Hall, 2nd Edition