Ιεραρχία Τσόμσκι

To 1956 ο Νόαμ Τσόμσκι ταξινόμησε τις τυπικές γραμματικές σε ιεραρχία με κριτήριο τους τύπους των κανόνων παραγωγής τους.

Μια τυπική γλώσσα G αποτελείται από

• Ένα πεπερασμένο σύνολο V από μη τερματικά σύμβολα
• Ένα πεπερασμένο σύνολο Τ από τερματικά σύμβολα
• Ένα πεπερασμένο σύνολο P από κανόνες παραγωγής
• Ένα αρχικό σύμβολο S

όπου,

• $V\cap T=\emptyset$
• $S\in V$.

Έτσι, μια τυπική γραμματική συμβολίζεται G(V,T,P,S).

Το επίπεδο ιεραρχίας των γραμματικών χαμηλώνει καθώς προχωράμε από τον τύπο 0 ως 3. Σύμφωνα με την ιεραρχία του Τσόμσκι:

Στις γραμματικές τύπου 0 ανήκουν οι γενικές γραμματικές. Η μορφή των κανόνων παραγωγής είναι

$a\to \beta ,a\neq \epsilon$, όπου $a,\beta \in (V\cup T)^{*}$.

Σε αυτήν την περίπτωση, οι συμβολοσειρές των κανόνων παραγωγής μπορούν να αποτελούνται από οποιαδήποτε σύμβολα της αλφαβήτου της γλώσσας.

Στις γραμματικές τύπου 1 ανήκουν οι γραμματικές με συμφραζόμενα (context sensitive grammar) ή μονοτονικές γραμματικές (monotonic grammar). Η μορφή των κανόνων παραγωγής είναι

$a\to \beta$, με $|a|\leq |\beta |$, όπου $a,\beta \in (V\cup T)^{*}$ και επιτρέπεται $S\to \epsilon$.

Και πάλι οι συμβολοσειρές α και β μπορούν να αποτελούνται από οποιαδήποτε σύμβολα της αλφαβήτου, αλλά πρέπει το μήκος της συμβολοσειράς α να είναι μικρότερο ή ίσο από αυτό της β.

Στις γραμματικές τύπου 2 ανήκουν οι γραμματικές χωρίς συμφραζόμενα (context free grammar) και η μορφή των κανόνων παραγωγής τους είναι

$A\to a$, όπου $A\in V$ και $a\in (V\cup T)^{*}$.

Εδώ, η συμβολοσειρά Α δεν επιτρέπεται να περιέχει τερματικά σύμβολα, ενώ η α μπορεί να έχει οποιαδήποτε σύμβολα.

Στις γραμματικές τύπου 3 ανήκουν οι κανονικές γραμματικές και η μορφή των κανόνων παραγωγής τους είναι δεξιογραμμικές (right-linear) ή αριστερογραμμικές (left-linear). Αν είναι δεξιογραμμικές, τότε

$A\to u,B\to uB$

Ενώ, αν είναι αριστερογραμμική, τότε

$A\to u,B\to Bu$, όπου $A,B\in V$ και $u\in T^{*}$.

Στις τύπου 3 γραμματικές, το πρώτο μέλος του κανόνα παραγωγής αποτελείται μόνο από μη τερματικά σύμβολα, ενώ το δεύτερο μέλος πρέπει να περιέχει και τερματικά σύμβολα.