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

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

Ορισμός[Επεξεργασία | επεξεργασία κώδικα]

Επί ενός αλφαβήτου $\Sigma$ , ως $\Sigma ^{*}$ ορίζεται το σύνολο όλων των συμβολοσειρών που δημιουργούνται με τα σύμβολα του $\Sigma$ , περιλαμβάνοντας και την κενή συμβολοσειρά.

Τυπικές Γλώσσες[Επεξεργασία | επεξεργασία κώδικα]

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

$L^{*}=\{w\in \Sigma ^{*}\ \colon \ w_{1}\circ \ ...\circ \ w_{k}\}$ για κάποιο $k\geq 0$ και $w_{1},\ ...,\ w_{k}\in L$

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

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

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

όπου

$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.

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

Πηγές[Επεξεργασία | επεξεργασία κώδικα]

↑ Σημειώνεται ότι αν και η προφορά του ονόματός του θα αναμενόταν να είναι Κλίνι, ο ίδιος χρησιμοποιούσε τη προφορά Κλέινι
↑ H.R. Lewis, C.H. Papadimitriou, Elements of the Theory of Computation, Prentice Hall, 2nd Edition, σελ.45-46

Βλέπε επίσης[Επεξεργασία | επεξεργασία κώδικα]

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

[1] Σημειώνεται ότι αν και η προφορά του ονόματός του θα αναμενόταν να είναι Κλίνι, ο ίδιος χρησιμοποιούσε τη προφορά Κλέινι

[2] H.R. Lewis, C.H. Papadimitriou, Elements of the Theory of Computation, Prentice Hall, 2nd Edition, σελ.45-46

[1]

[2]