Κανονικές εκφράσεις

Η κανονική έκφραση είναι μια συμβολοσειρά που μας επιτρέπει να περιγράψουμε ένα σύνολο λέξεων. Τις κανονικές εκφράσεις μπορούμε επίσης να τις δούμε ως έναν απλό τρόπο περιγραφής ενός πεπερασμένου αυτομάτου.

Τι είναι η κανονική έκφραση

Στην αριθμητική χρησιμοποιούμε σύμβολα όπως τα · και + για να σχηματίσουμε μια παράσταση, για παράδειγμα (2 + 3) · 4. Υπολογίζοντας αυτή την παράσταση παίρνουμε έναν αριθμό. Η κανονική έκφραση είναι μια ακολουθία χαρακτήρων και μερικών ειδικών συμβόλων, π.χ. a(x ∪ y), και το αποτέλεσμα του υπολογισμού της είναι μια (τυπική) γλώσσα. Αποτέλεσμα της παράστασης (2 + 3) · 4 είναι ο αριθμός 20, ενώ αποτέλεσμα της κανονικής έκφρασης a(x ∪ y) είναι το σύνολο των δύο λέξεων «ax», «ay».

Πώς θα υπολογίζαμε την προηγούμενη κανονική έκφραση a(x ∪ y); Κάθε γράμμα είναι στην πραγματικότητα συντομογραφία ενός μονοσύνολου που περιέχει το συγκεκριμένο γράμμα, και ο εννοούμενος πολλαπλασιασμός είναι παράθεση λέξεων. Την κανονική έκφραση θα μπορούσαμε να τη γράψουμε «αναλυτικά» ως εξής:

$$\left\{a\right\}\circ (\left\{x\right\}\cup \left\{y\right\})$$

Στη συνέχεια θα την υπολογίζαμε ως εξής: η ένωση {x} ∪ {y} μας δίνει τη γλώσσα {x,y}. Με την παράθεση των γλωσσών {a} και {x,y} παίρνουμε τη γλώσσα {ax, ay}.

Οι κανονικές εκφράσεις χρησιμοποιούνται πολύ συχνά στον προγραμματισμό και οι περισσότερες γλώσσες προγραμματισμού τις υλοποιούν με κάποιον τρόπο. Οι κανονικές εκφράσεις χρησιμοποιούνται έτσι, για παράδειγμα, για να ελέγξουμε αν ένα κείμενο που πληκτρολόγησε ο χρήστης πληροί ορισμένα κριτήρια (π.χ. αν είναι έγκυρο email, έγκυρη ημερομηνία κ.λπ.), καθώς και για αντικατάσταση κειμένων (π.χ. μπορεί να θέλουμε να αντικαταστήσουμε όλες τις εμφανίσεις URL σε ένα κείμενο με συνδέσμους στους οποίους μπορούμε να κάνουμε κλικ κ.λπ.).

Οι πραγματικές υλοποιήσεις των κανονικών εκφράσεων είναι συνήθως ισχυρότερες από τις κανονικές εκφράσεις που περιγράφονται εδώ και χρησιμοποιούν ελαφρώς διαφορετική, αλλά κυρίως πιο σύνθετη σύνταξη.

Ορισμός της κανονικής έκφρασης

Την κανονική έκφραση θα την ορίσουμε πάνω σε ένα αλφάβητο Σ. Τότε λέμε ότι κανονική έκφραση είναι:

1. a, όπου a ∈ Σ. Δηλαδή ένας μεμονωμένος χαρακτήρας του αλφαβήτου είναι κανονική έκφραση.
2. ϵ: η κενή λέξη, που στον προγραμματισμό γράφεται και ως κενά εισαγωγικά «».
3. ∅: η κανονική έκφραση πρέπει να μπορεί να περιγράφει και την κενή γλώσσα, άρα η κενή γλώσσα είναι κανονική έκφραση.
4. (R₁ ∪ R₂), όπου R₁, R₂ είναι κανονικές εκφράσεις.
5. (R₁ ∘ R₂), όπου R₁, R₂ είναι κανονικές εκφράσεις.
6. (R^∗), όπου R είναι κανονική έκφραση.

Αντί για το σύμβολο ∪ του σημείου 4 μπορούμε να χρησιμοποιούμε και το σύμβολο της κατακόρυφης γραμμής: |. Αντί για το σύμβολο ∘ δεν χρειάζεται να χρησιμοποιούμε τίποτα. Όπως συνήθως δεν γράφουμε ρητά το σύμβολο του πολλαπλασιασμού, την τελεία ·, έτσι συνήθως δεν γράφουμε ούτε το σύμβολο της παράθεσης ∘. Αυτές οι κανονικές εκφράσεις είναι λοιπόν ταυτόσημες: a ∘ (b ∪ c) και a(b|c).

Τι σημαίνουν οι επιμέρους τελεστές;

• ∪ ή | δηλώνει την ένωση γλωσσών.
• ∘ δηλώνει την παράθεση γλωσσών.
• ^∗ δηλώνει την κλειστότητα Kleene μιας γλώσσας.

Παραδείγματα:

• Το a δηλώνει την απλή γλώσσα {a}.
• Το a|b δηλώνει τη γλώσσα που αποτελείται από τις δύο λέξεις {a, b}.
• Το a ∘ b δηλώνει τη γλώσσα {ab}.
• Το a(b|c)d δηλώνει τη γλώσσα {abd, acd}.
• Το a(b^∗) δηλώνει τη γλώσσα όλων των λέξεων που αρχίζουν με το γράμμα «a», μετά το οποίο ακολουθεί οποιοδήποτε πλήθος γραμμάτων «b».
• Το (ab)^∗ δηλώνει τη γλώσσα όλων των λέξεων {ϵ, ab, abab, ababab, …}.
• Το 0^∗10^∗ δηλώνει τη γλώσσα όλων των δυαδικών λέξεων που περιέχουν ακριβώς μία μονάδα. (Πρόσεξε ότι ακριβέστερο θα ήταν να γράψουμε αυτή την έκφραση ως εξής: (0^∗)1(0^∗), αλλά όταν ο συμβολισμός είναι ευανάγνωστος και χωρίς αυτές, μπορούμε να παραλείψουμε τις παρενθέσεις.)
• Το Σ^∗1Σ^∗ δηλώνει τη γλώσσα όλων των λέξεων που περιέχουν τουλάχιστον μία μονάδα.
• Το (1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)^∗ δηλώνει τη γλώσσα όλων των θετικών ακεραίων.

Στη συνέχεια θα δούμε την ισοδυναμία ανάμεσα στις κανονικές εκφράσεις και τα πεπερασμένα αυτόματα. Για κάθε κανονική έκφραση, της οποίας ο υπολογισμός δίνει τη γλώσσα R, υπάρχει πεπερασμένο αυτόματο A για το οποίο ισχύει L(A) = R, και αντίστροφα.

Πηγές

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools