Αστέρι Κλέινι

Στα Μαθηματικά, στη λογική, και στην επιστήμη υπολογιστών, το **Αστέρι Κλέινι** (Kleene star), ή η **κλειστότητα Κλέινι** (Kleene closure), είναι μια πράξη με ένα όρισμα, που εφαρμόζεται σε σύνολα συμβόλων ή χαρακτήρων ή σε συμβολοσειρές. Η εφαρμογή του Αστεριού Κλέινι σε ένα σύνολο *V* συμβολίζεται ως *V**. Χρησιμοποιείται ευρύτατα για κανονικές εκφράσεις, αφού ειδικά για το σκοπό αυτόν το εισήγαγε ο Στίβεν Κλέινι (Stephen Kleene), όταν χαρακτήρισε ορισμένα αυτόματα.

## Ορισμός
Επί ενός αλφαβήτου **<math>\Sigma</math>**, ως **<math>\Sigma ^*</math>** ορίζεται το σύνολο όλων των συμβολοσειρών που δημιουργούνται με τα σύμβολα του **<math>\Sigma</math>**, περιλαμβάνοντας και την κενή συμβολοσειρά.

## Τυπικές Γλώσσες
Εξ ορισμού το αστέρι Κλέινι είναι πράξη που μπορεί να εφαρμόζεται σε τυπικές γλώσσες. Έστω γλώσσα L, τότε L^* είναι το σύνολο συμβολοσειρών που προκύπτει από τη συνένωση μηδέν ή περισσότερων συμβολοσειρών της L. Επομενως:

L^* = \{ w \in \Sigma ^*\ \colon \ w_1 \circ \ ... \circ \ w_k \}  για κάποιο  k \ge 0  και w_1,\ ...,\ w_k \in L

όπου w κάποια συμβολοσειρά.

Με βάση το Αστέρι Κλέινι ορίζεται και η πράξη που συμβολίζεται με ^+ και περιγράφει τη συνένωση (concatenation) LL^*, οριζόμενη ως ακολούθως:

L^+ = \{ w \in \Sigma ^*\ \colon \ w_1 \circ \ ... \circ \ w_k \}  για κάποιο  k \ge 1  και w_1,\ ...,\ w_k \in L

όπου 
* L η γλώσσα,
* ^* το Αστέρι Κλέινι,
* w κάποια συμβολοσειρά.

Δηλαδή η **<math>L^+</math>** είναι η μικρότερη γλώσσα που περιέχει την L και όλες τις συμβολοσειρές που προκύπτουν με συνένωση (concatenation). Σημειώνεται ότι L^+ είναι η κλειστότητα της L^+ υπό την πράξη της συνένωσης.

## Παραδείγματα
Εφαρμογή αστεριού Κλέινι σε σύνολο στοιχειοσειρών :
: {"ab", "c"}* = {&epsilon;, "ab", "c", "abab", "abc", "cab", "cc", "ababab", "ababc", "abcab", "abcc", "cabab", "cabc", "ccab", "ccc", ...}

Εφαρμογή αστεριού Κλέινι σε σύνολο χαρακτήρων :
: {'a', 'b', 'c'}* = {&epsilon;, "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*))
* (Ουδέτερο στοιχείο) : υπάρχει ένα *&epsilon;* που ανήκει στο *M*, τέτοιο ώστε για κάθε *a* που ανήκει στο *M* ισχύει ότι (*a* . *&epsilon;*) = (*&epsilon;* . *a*) = *a*

Αν το *V* είναι ένα υποσύνολο του *M*, τότε το *V** ορίζεται ως το μικρότερο υπερσύνολο του *V* που περιέχει το &epsilon; (την κενή στοιχειοσειρά) και είναι κλειστό για την περιγραφείσα πράξη. Το *V** είναι επίσης ένα μονοειδές, και ονομάζεται *μονοειδές παραγόμενο από το V*.

Αυτή είναι γενίκευση του αστεριού Κλέινι που περιγράφτηκε προηγουμένως αφού το σύνολο όλων των στοιχειοσειρών που σχηματίζονται από κάποιο σύνολο συμβόλων είναι ένα μονοειδές (με ορισμένη πράξη την συναλύσωση στοιχειοσειρών).

## Πηγές




## Δείτε επίσης
* Άλγεβρα Κλέινι (Kleene algebra)
* Μορφή Μπάκους-Νάουρ
* Εκτεταμένη μορφή Μπάκους-Νάουρ (Extended Backus-Naur form)
* Λήμμα αντλίας (Pumping Lemma)
* Πρόβλημα ύψους αστεριού (Star height problem), Γενικευμένο πρόβλημα ύψους αστεριού, Γλώσσα χωρίς αστέρια (star-free language)

Κατηγορία:Τυπικές γλώσσες