Διαφορά μεταξύ των αναθεωρήσεων του «Ιεραρχία Τσόμσκι»

Μετάβαση στην πλοήγηση Πήδηση στην αναζήτηση
μ
Σύμφωνα με την ιεραρχία του Τσόμσκι:
 
===Γενικές Γραμματικές===
Στις γραμματικές '''τύπου 0''' ανήκουν οι [[Γενική γραμματική|γενικές γραμματικές]]. Η μορφή των κανόνων παραγωγής είναι
:<math>a \to \beta, a \neq \epsilon</math>, όπου <math>a,\beta \in (V \cup T)^{*}</math>.
Σε αυτήν την περίπτωση, οι [[συμβολοσειρά|συμβολοσειρές]] των κανόνων παραγωγής μπορούν να αποτελούνται από οποιαδήποτε σύμβολα της αλφαβήτου της γλώσσας.
 
===Γραμματικές Με Συμφραζόμενα===
Στις γραμματικές '''τύπου 1''' ανήκουν οι [[Γραμματική με συμφραζόμενα|γραμματικές με συμφραζόμενα]] (context sensitive grammar) ή μονοτονικές γραμματικές (monotonic grammar). Η μορφή των κανόνων παραγωγής είναι
:<math>a \to \beta</math>, με <math>|a| \leq |\beta|</math>, όπου <math>a,\beta \in (V \cup T)^{*}</math> και επιτρέπεται <math>S \to \epsilon</math>.
Και πάλι οι συμβολοσειρές α και β μπορούν να αποτελούνται από οποιαδήποτε σύμβολα της αλφαβήτου, αλλά πρέπει το μήκος της συμβολοσειράς α να είναι μικρότερο ή ίσο από αυτό της β.
 
===Γραμματικές Χωρίς Συμφραζόμενα===
Στις γραμματικές '''τύπου 2''' ανήκουν οι [[Γραμματική χωρίς συμφραζόμενα|γραμματικές χωρίς συμφραζόμενα]] (context free grammar) και η μορφή των κανόνων παραγωγής τους είναι
:<math>A \to a</math>, όπου <math>A \in V</math> και <math>a \in (V \cup T)^*</math>.
Εδώ, η συμβολοσειρά Α δεν επιτρέπεται να περιέχει τερματικά σύμβολα, ενώ η α μπορεί να έχει οποιαδήποτε σύμβολα.
 
===Κανονικές Γραμματικές===
Στις γραμματικές '''τύπου 3''' ανήκουν οι [[Κανονική γραμματική|κανονικές γραμματικές]] και η μορφή των κανόνων παραγωγής τους είναι δεξιογραμμικές (right-linear) ή αριστερογραμμικές (left-linear). Αν είναι δεξιογραμμικές, τότε
:<math>A \to u, B \to uB</math>
2.199

επεξεργασίες

Μενού πλοήγησης