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

καμία σύνοψη επεξεργασίας
(εσωτερικοί σύνδεσμοι)
To [[1956]] ο [[Νόαμ Τσόμσκι|Avram Noam Chomsky]] ταξινόμησε τις [[τυπική γραμματική|τυπικές γραμματικές]] σε ιεραρχία με κριτήριο τους τύπους των κανόνων παραγωγής τους.
 
Μια τυπική γλώσσα G αποτελείται από
:<math>a \to \beta, a \neq \epsilon</math>, όπου <math>a,\beta \in (V \cup T)^{*}</math>.
 
Στις γραμματικές '''τύπου 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>.
 
Στις γραμματικές '''τύπου 2''' ανήκουν οι [[ΓραμμτικήΓραμματική χωρίς συμφραζόμενα|γραμματικές χωρίς συμφραζόμενα]] (context free grammar) και η μορφή των κανόνων παραγωγής τους είναι
:<math>A \to a</math>, όπου <math>A \in V</math> και <math>a \in (V \cup T)^*</math>.
 
80.160

επεξεργασίες