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

To [[1956]] ο [[Νόαμ Τσόμσκι]] ταξινόμησε τις [[τυπική γραμματική|τυπικές γραμματικές]] σε ιεραρχία με κριτήριο τους τύπους των κανόνων παραγωγής τους. Η '''ιεραρχία Τσόμσκι''', όπως ονομάστηκε, θεωρείται πολύ χρήσιμη στο πεδίο της [[Επιστήμη υπολογιστών|επιστήμης υπολογιστών]].

 

{{Κύριο|Τυπική γραμματική}}

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

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

 

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

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

 

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

:<math>a \to \beta, a \neq \epsilon</math>, όπου <math>a,\beta \in (V \cup T)^{*}</math>.

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

 

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

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

 

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

:<math>A \to a</math>, όπου <math>A \in V</math> και <math>a \in (V \cup T)^*</math>.

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

 

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

:<math>A \to u, B \to uB</math>

{{επέκταση}}

 

 

[[af:Chomsky-hiërargie]]

[[ca:Jerarquia de Chomsky]]

[[cs:Chomského hierarchie]]

[[en:Chomsky hierarchy]]

[[es:Jerarquía de Chomsky]]