Ιεραρχία Τσόμσκι: Διαφορά μεταξύ των αναθεωρήσεων
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
Vevek (συζήτηση | συνεισφορές) |
Vevek (συζήτηση | συνεισφορές) |
||
Γραμμή 21:
Στις γραμματικές '''τύπου 0''' ανήκουν οι [[Γενική γραμματική|γενικές γραμματικές]]. Η μορφή των κανόνων παραγωγής είναι
:<math>a \to \beta, a \neq \epsilon</math>, όπου <math>a,\beta \in (V \cup T)^{*}</math>.
Σε αυτήν την περίπτωση, οι [[συμβολοσειρά|συμβολοσειρές]] των κανόνων παραγωγής μπορούν να αποτελούνται από οποιαδήποτε σύμβολα της αλφαβήτου της γλώσσας. Από μια οποιαδήποτε συμβολοσειρά (εκτός της κενής) μπορεί να παραχθεί οποιαδήποτε άλλη (ή και η ίδια) συμβολοσειρά. Οι γενικές γραμματικές είναι γραμματικές με μόνο περιορισμό ότι από το κενό σύμβολο δεν παράγεται συμβολοσειρά. Επειδή δεν υπάρχουν άλλοι περιορισμοί, το σύνολο των γλωσσών που ανήκουν στις γενικές γραμματικές είναι το πιο ευρύ (συγκριτικά με τις υπόλοιπες γραμματικές της Ιεραρχίας Τσόμσκι) και μέσα σε αυτό εμπεριέχονται τα σύνολα των γλωσσών που ανήκουν στις γραμματικές χαμηλότερης ιεραρχίας.
Οι γενικές γραμματικές αναγνωρίζονται από τις [[Μηχανή Τούρινγκ|Μηχανές Τούρινγκ]] (Turing Machines).
| |||