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

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)^{*}$.

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

Οι γενικές γραμματικές αναγνωρίζονται από τις Μηχανές Τούρινγκ (Turing Machines).

Γραμματικές Με Συμφραζόμενα

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

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

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

Τα αυτόματα που αναγνωρίζουν γραμματικές χωρίς συμφραζόμενα είναι τα Γραμμικά Περιορισμένα Αυτόματα (Linearly Bounded Automata).

Γραμματικές Χωρίς Συμφραζόμενα

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

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

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

Τα αυτόματα που αναγνωρίζουν γραμματικές χωρις συμφαζόμενα είναι τα Αυτόματα Στοίβας (Push Down Automata).

Κανονικές Γραμματικές

Στις γραμματικές τύπου 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 γραμματικές, το πρώτο μέλος του κανόνα παραγωγής αποτελείται μόνο από μη τερματικά σύμβολα, ενώ το δεύτερο μέλος πρέπει να περιέχει και τερματικά σύμβολα.

Τις κανονικές γραμματικές αναγνωρίζουν τα Πεπερασμένα Αυτόματα ή Αναγνωριστές Πεπερασμένων Καταστάσεων (Finite State Acceptors).