Κανονική έκφραση
Το λήμμα παραθέτει τις πηγές του αόριστα, χωρίς παραπομπές. |
Οι κανονικές εκφράσεις ή κανονικές παραστάσεις (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
Εξωτερικοί σύνδεσμοι
🔥 Top keywords: Πύλη:ΚύριαFacebookΜαρίνα ΨάλτηΟΥΕΦΑ Τσάμπιονς ΛιγκΕιδικό:ΑναζήτησηΘάλασσα των ΣαργασσώνΓιάννης ΦέρτηςΝίκος ΠαπάζογλουΣύνδρομο ΤέρνερΡεάλ ΜαδρίτηςΦρέντι ΜπελέρηςΕλεονώρα ΜελέτηΚάρλο ΑντσελότιΜάντσεστερ ΣίτιΟλυμπιακή ΦλόγαΙράνΠρώτο ΘέμαΔημήτρης ΜητροπάνοςΜαρία ΚάλλαςΜαρίνα ΣάττιYouTubeΠεπ ΓκουαρδιόλαΝτουμπάιΜπάγερν ΜονάχουΙσραήλΘερινοί Ολυμπιακοί Αγώνες 2024Βραβείο Νόμπελ ΕιρήνηςΞένια ΚαλογεροπούλουΠύρρος ΔήμαςΕλλάδαΓιώργος ΜπαρτζώκαςΑντρίι ΛούνινΟλυμπιακοί ΑγώνεςΜΑΒΗ (παραστρατιωτική οργάνωση)Τζουντ ΜπέλινγκχαμΤαυρίνηΦώτης ΙωαννίδηςΣτανοζολόληΆγιος Ιάκωβος Τσαλίκης