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

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

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

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

Κανονικές εκφράσεις επί του ορίζονται ως όλες οι συμβολοσειρές (strings) επί του που σχηματίζονται ακολούθως:

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

όπου

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


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

Παραδείγματα[Επεξεργασία | επεξεργασία κώδικα]

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

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

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

  • H.R. Lewis, C.H. Papadimitriou, Elements of the Theory of Computation, Prentice Hall, 2nd Edition

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