Αστέρι Κλέινι: Διαφορά μεταξύ των αναθεωρήσεων
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
μΧωρίς σύνοψη επεξεργασίας |
|||
Γραμμή 2:
==Ορισμός==
▲# Επί ενός αλφαβήτου '''<math>\Sigma</math>''', ως '''<math>\Sigma ^*</math>''' ορίζεται το σύνολο όλων των [[συμβολοσειρά|συμβολοσειρών]] που δημιουργούνται με τα σύμβολα του '''<math>\Sigma</math>''', περιλαμβάνοντας και την κενή συμβολοσειρά.
==Τυπικές Γλώσσες==
Εξ ορισμού το αστέρι Κλήνυ είναι πράξη που μπορεί να εφαρμόζεται σε [[τυπική γλώσσα|τυπικές γλώσσες]]. Έστω γλώσσα <math>L</math>, τ<ότε <math>L^*</math> είναι το σύνολο συμβολοσειρών που προκύπτει από τη συναλύσωση μηδέν ή περισσότερων συμβολοσειρών της <math>L</math>. Επομενως:
<math>L^* = \{ w \in \Sigma ^*\ \colon \ w_1 \circ \ ... \circ \ w_k \} </math> για κάποιο <math> k \ge 0 </math> και <math>w_1,\ ...,\ w_k \in L</math>
όπου w κάποια συμβολοσειρά.
Με βάση το Αστέρι Κλήνυ ορίζεται και η πράξη που συμβολίζεται με <math>^+</math> και περιγράφει τη συναλύσωση (concatenation) <math>LL^*</math>, οριζόμενη ως ακολούθως:
<math>L^* = \{ w \in \Sigma ^*\ \colon \ w_1 \circ \ ... \circ \ w_k \} </math> για κάποιο <math> k \ge 1 </math> και <math>w_1,\ ...,\ w_k \in L</math>
όπου
* <math>L</math> η γλώσσα,
* <math>^*</math> το Αστέρι Κλήνυ,
* <math>w</math> κάποια συμβολοσειρά.
Δηλαδή η '''<math>L^+</math>''' είναι η μικρότερη γλώσσα που περιέχει την <math>L</math> και όλες τις συμβολοσειρές που προκύπτουν με συναλύσωση (concatenation). Σημειώνεται ότι <math>L^+</math> είναι η [κλειστότητα]] της <math>L^+</math> υπό την πράξη της [[Συμβολοσειρά|συναλύσωσης]]. <ref></ref>
==Παραδείγματα==
| |||