Αστέρι Κλέινι
Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Στα Μαθηματικά, στην Λογική, και στην Επιστήμη Υπολογιστών, το Αστέρι Κλέινι (Kleene star), ή η κλειστότητα Κλέινι (Kleene closure), είναι μια πράξη με ένα όρισμα, που εφαρμόζεται σε σύνολα συμβόλων ή χαρακτήρων ή σε στοιχειοσειρές. Η εφαρμογή του Αστεριού Κλέινι σε ένα σύνολο V συμβολίζεται ως V*. Χρησιμοποιείται ευρύτατα για κανονικές εκφράσεις, αφού ειδικά για το σκοπό αυτόν το εισήγαγε ο Στέφεν Κλέινι (Stephen Kleene)[1], όταν χαρακτήρισε ορισμένα αυτόματα.
Πίνακας περιεχομένων |
[Επεξεργασία] Ορισμός
Επί ενός αλφαβήτου Σ, ως Σ * ορίζεται το σύνολο όλων των συμβολοσειρών που δημιουργούνται με τα σύμβολα του Σ, περιλαμβάνοντας και την κενή συμβολοσειρά.
[Επεξεργασία] Τυπικές Γλώσσες
Εξ ορισμού το αστέρι Κλέινι είναι πράξη που μπορεί να εφαρμόζεται σε τυπικές γλώσσες. Έστω γλώσσα L, τότε L * είναι το σύνολο συμβολοσειρών που προκύπτει από τη συναλύσωση μηδέν ή περισσότερων συμβολοσειρών της L. Επομενως:
για κάποιο
και
όπου w κάποια συμβολοσειρά.
Με βάση το Αστέρι Κλέινι ορίζεται και η πράξη που συμβολίζεται με + και περιγράφει τη συναλύσωση (concatenation) LL * , οριζόμενη ως ακολούθως:
για κάποιο
και
όπου
- L η γλώσσα,
- * το Αστέρι Κλέινι,
- w κάποια συμβολοσειρά.
Δηλαδή η L + είναι η μικρότερη γλώσσα που περιέχει την L και όλες τις συμβολοσειρές που προκύπτουν με συναλύσωση (concatenation). Σημειώνεται ότι L + είναι η [κλειστότητα]] της L + υπό την πράξη της συναλύσωσης. [2]
[Επεξεργασία] Παραδείγματα
Εφαρμογή αστεριού Κλέινι σε σύνολο στοιχειοσειρών :
- {"ab", "c"}* = {ε, "ab", "c", "abab", "abc", "cab", "cc", "ababab", "ababc", "abcab", "abcc", "cabab", "cabc", "ccab", "ccc", ...}
Εφαρμογή αστεριού Κλέινι σε σύνολο χαρακτήρων :
- {'a', 'b', 'c'}* = {ε, "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc", ...}
[Επεξεργασία] Γενίκευση
Το αστέρι Κλέινι συχνά γενικεύεται για οποιοδήποτε Μονοειδές (monoid) (M, .).
Μονοειδές είναι ένα σύνολο M, για τα στοιχεία του οποίου είναι ορισμένη μιά πράξη (μαθηματικά) με δύο ορίσματα '.', η οποία έχει τις εξής ιδιότητες :
- (Κλειστότητα) : για κάθε a και b που ανήκουν στο M ισχύει ότι το (a . b) ανήκει στο M
- (Προσεταιρισμός) : για κάθε a, b και c που ανήκουν στο M ισχύει ότι ((a . b) . c) = (a . (b . c))
- (Ουδέτερο στοιχείο) : υπάρχει ένα ε που ανήκει στο M, τέτοιο ώστε για κάθε a που ανήκει στο M ισχύει ότι (a . ε) = (ε . a) = a
Αν το V είναι ένα υποσύνολο του M, τότε το V* ορίζεται ως το μικρότερο υπερσύνολο του V που περιέχει το ε (την κενή στοιχειοσειρά) και είναι κλειστό για την περιγραφείσα πράξη. Το V* είναι επίσης ένα μονοειδές, και ονομάζεται μονοειδές παραγόμενο από το V.
Αυτή είναι γενίκευση του αστεριού Κλέινι που περιγράφτηκε προηγουμένως αφού το σύνολο όλων των στοιχειοσειρών που σχηματίζονται από κάποιο σύνολο συμβόλων είναι ένα μονοειδές (με ορισμένη πράξη την συναλύσωση στοιχειοσειρών).
[Επεξεργασία] Πηγές
[Επεξεργασία] Βλέπε επίσης
- Άλγεβρα Κλέινι (Kleene algebra)
- Εκτεταμένη μορφή Μπάκους-Ναούρ (Extended Backus-Naur form)
- Λήμμα αντλίας (Pumping Lemma)
- Πρόβλημα ύψους αστεριού (Star height problem), Γενικευμένο πρόβλημα ύψους αστεριού, Γλώσσα χωρίς αστέρια (star-free language)