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

εσωτερικοί σύνδεσμοι
(λίγα λόγια για την ιεραρχία Τσόμσκι)
 
(εσωτερικοί σύνδεσμοι)
To 1956 ο [[Νόαμ Τσόμσκι|Avram Noam Chomsky]] ταξινόμησε τις [[τυπική γραμματική|τυπικές γραμματικές]] σε ιεραρχία με κριτήριο τους τύπους των κανόνων παραγωγής τους.
 
Μια τυπική γλώσσα G αποτελείται από
* Ένα πεπερασμένο [[σύνολο]] V από μη τερματικά σύμβολα
* Ένα πεπερασμένο σύνολο Τ από τερματικά σύμβολα
* Ένα πεπερασμένο σύνολο P από κανόνες παραγωγής
Σύμφωνα με την ιεραρχία του Τσόμσκι:
 
Στις γραμματικές '''τύπου 0''' ανήκουν οι ''[[Γενική γραμματική|γενικές γραμματικές'']]. Η μορφή των κανόνων παραγωγής είναι
:<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>.
 
Στις γραμματικές '''τύπου 3''' ανήκουν οι '''κανονικές[[Κανονική (regular)γραμματική|κανονικές γραμματικές''']] και η μορφή των κανόνων παραγωγής τους είναι δεξιογραμμικές (right-linear) ή αριστερογραμμικές (left-linear). Αν είναι δεξιογραμμικές, τότε
:<math>A \to u, B \to uB</math>
Ενώ, αν είναι αριστερογραμμική, τότε
435

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