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

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).