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

μ
Ρομπότ: Προσθήκη: de:Chomsky-Hierarchie; διακοσμητικές αλλαγές
μ (Ρομπότ: Προσθήκη: de:Chomsky-Hierarchie; διακοσμητικές αλλαγές)
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]]
[[de:Chomsky-Hierarchie]]
[[en:Chomsky hierarchy]]
[[es:Jerarquía de Chomsky]]