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

Σύμφωνα με την ιεραρχία του Τσόμσκι:

 

Στις γραμματικές '''τύπου 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>