Αστέρι Κλέινι
Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Στα Μαθηματικά, στην Λογική, και στην Επιστήμη Υπολογιστών, το Αστέρι Κλέινι (Kleene star), ή η κλειστότητα Κλέινι (Kleene closure), είναι μια πράξη με ένα όρισμα, που εφαρμόζεται σε σύνολα συμβόλων ή χαρακτήρων ή σε στοιχειοσειρές. Η εφαρμογή του Αστεριού Κλέινι σε ένα σύνολο V συμβολίζεται ως V*. Χρησιμοποιείται ευρύτατα για κανονικές εκφράσεις, αφού ειδικά για τον σκοπό αυτό το εισήγαγε ο Στέφεν Κλέινι (Stephen Kleene) όταν χαρακτήρισε ορισμένα αυτόματα.
- Αν το V είναι ένα σύνολο στοιχειοσειρών, τότε το V* ορίζεται ότι είναι το μικρότερο υπερσύνολο του V που περιέχει το ε (την κενή στοιχειοσειρά) και είναι κλειστό στην πράξη συναλύσωση στοιχειοσειρών. Το σύνολο αυτό μπορεί επίσης να περιγραφεί ως το σύνολο των στοιχειοσειρών που μπορούν να δημιουργηθούν με συναλύσωση n στοιχειοσειρών του V, με n >= 0.
- Αν το V είναι ένα σύνολο συμβόλων ή χαρακτήρων, τότε το V* είναι το σύνολο όλων των στοιχειοσειρών που δημιουργούνται με τα σύμβολα του V, περιλαμβάνοντας και την κενή στοιχειοσειρά.
[Επεξεργασία] Παραδείγματα
Εφαρμογή αστεριού Κλέινι σε σύνολο στοιχειοσειρών :
- {"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)