Θεωρία υπολογισμού: Διαφορά μεταξύ των αναθεωρήσεων
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
Αναίρεση έκδοσης 5527746 από τον 81.186.191.179 (Συζήτηση) |
|||
Γραμμή 29:
''[[Αστέρι Κλέινι]]'' ή ''κλειστότητα Κλέινι'' (Kleene Star) ενός αλφαβήτου Σ ονομάζουμε το σύνολο Σ* όλων των δυνατών [[συμβολοσειρά|συμβολοσειρών]] που προκύπτουν από αυτό το αλφάβητο. Πρόκειται για ένα μετρήσιμο [[σύνολο|απειροσύνολο]] (''Συμπέρασμα 1''). Γλώσσα ονομάζουμε ένα [[υποσύνολο]] του Σ* για δεδομένο αλφάβητο Σ. Το σύνολο όλων των γλωσσών που προκύπτουν από ένα αλφάβητο Σ είναι το [[δυναμοσύνολο]] (το σύνολο όλων των δυνατών υποσυνόλων) του Σ* και είναι μη μετρήσιμο απειροσύνολο (''Συμπέρασμα 2''). Μπορούμε να καταλήξουμε σε διάφορους πεπερασμένους τρόπους αναπαράστασης γλωσσών (ασχέτως του αν οι ίδιες οι γλώσσες είναι πεπερασμένες ή άπειρες), όμως όλοι οδηγούν σε μία συμβολοσειρά ως τρόπο αναπαράστασης μίας γλώσσας. Όμως, δεδομένου ενός αλφαβήτου αναπαράστασης Σ, υπάρχουν μετρήσιμα άπειρες συμβολοσειρές αναπαράστασης (Συμπέρασμα 1) και μη μετρήσιμα άπειρες γλώσσες (Συμπέρασμα 2). Επομένως, αφού υπάρχουν περισσότερες γλώσσες απ' ότι αναπαραστάσεις, αναπόφευκτα θα υπάρχουν πάντα γλώσσες που δεν μπορούμε να αναπαραστήσουμε με πεπερασμένο τρόπο.
Υπάρχουν δύο ισοδύναμοι τρόποι περιγραφής μίας γλώσσας: είτε μέσω ενός παραγωγού γλώσσας, ενός εκφραστικού μηχανισμού που περιγράφει τις έγκυρες
:{| border="1" cellpadding="3" cellspacing="0"
|