Αστέρι Κλέινι: Διαφορά μεταξύ των αναθεωρήσεων

Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
Mmsoft (συζήτηση | συνεισφορές)
αλλαγή
Γραμμή 1:
Στα [[Μαθηματικά]], στην [[Λογική]], και στην [[Επιστήμη Υπολογιστών]], το '''Αστέρι Κλέινι''' (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", ...}
 
Γραμμή 14:
 
==Γενίκευση==
Το αστέρι Κλέινι συχνά γενικεύεται για οποιοδήποτε [[Μονοειδές]] (monoid) (''M'', .), δηλαδή, ένα σύνολο ''M'' και την πράξη με δύο ορίσματα '.' για τα στοιχεία του ''M'', με ιδιότητες :
* ([[Κλειστότητα]]), για κάθε ''a'' και ''b'' που ανήκουν στο ''M'' ισχύει ότι το ''a'' . ''b'' ανήκει στο ''M''
* ([[Προσεταιρισμός]]), για κάθε ''a'', ''b'' και ''c'' που ανήκουν στο ''M'' ισχύει ότι (''a'' . ''b'') . ''c'' = ''a'' . (''b'' . ''c'')
* ([[Ουδέτερο στοιχείο]]), υπάρχει ένα ''ε'' που ανήκει στο ''M'', τέτοιο ώστε για κάθε ''a'' να ισχύει ότι ''a'' . ''ε'' = ''ε'' . ''a'' = ''a''
 
''Μονοειδές'' είναι ένα σύνολο ''M'', για τα στοιχεία του οποίου είναι ορισμένη μιά ''πράξη'' με δύο ορίσματα '.', η οποία έχει τις εξής ιδιότητες :
Αν το ''V'' είναι ένα [[Υποσύνολο|υποσύνολο]] του ''M'', τότε το ''V''* ορίζεται ως το μικρότερο [[Υπερσύνολο|υπερσύνολο]] του ''V'' που περιέχει το ε (το κενό νήμα) και είναι κλειστό για την περιγραφείσα πράξη. Το ''V''* είναι επίσης ένα μονοειδές, και ονομάζεται ''μονοειδές παραγόμενο από το V''.
* ([[Κλειστότητα]]), : για κάθε ''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''.
Αυτή είναι γενίκευση του αστεριού Κλέινι που περιγράφτηκε προηγουμένως αφού το σύνολο όλων των νημάτων που σχηματίζονται από κάποιο σύνολο συμβόλων είναι ένα μονοειδές (με δυαδική πράξη την συναλύσωση νημάτων).
 
Αυτή είναι γενίκευση του αστεριού Κλέινι που περιγράφτηκε προηγουμένως αφού το σύνολο όλων των νημάτωνστοιχειοσειρών που σχηματίζονται από κάποιο σύνολο συμβόλων είναι ένα μονοειδές (με δυαδικήορισμένη πράξη την συναλύσωση νημάτωνστοιχειοσειρών).
 
==Δείτε επίσης==