Ιεραρχία Τσόμσκι: Διαφορά μεταξύ των αναθεωρήσεων
Vevek (συζήτηση | συνεισφορές) εσωτερικοί σύνδεσμοι |
Χωρίς σύνοψη επεξεργασίας |
||
Γραμμή 1: | Γραμμή 1: | ||
To 1956 ο [[Νόαμ Τσόμσκι |
To [[1956]] ο [[Νόαμ Τσόμσκι]] ταξινόμησε τις [[τυπική γραμματική|τυπικές γραμματικές]] σε ιεραρχία με κριτήριο τους τύπους των κανόνων παραγωγής τους. |
||
Μια τυπική γλώσσα G αποτελείται από |
Μια τυπική γλώσσα G αποτελείται από |
||
Γραμμή 18: | Γραμμή 18: | ||
:<math>a \to \beta, a \neq \epsilon</math>, όπου <math>a,\beta \in (V \cup T)^{*}</math>. |
:<math>a \to \beta, a \neq \epsilon</math>, όπου <math>a,\beta \in (V \cup T)^{*}</math>. |
||
Στις γραμματικές '''τύπου 1''' ανήκουν οι [[ |
Στις γραμματικές '''τύπου 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>. |
:<math>a \to \beta</math>, με <math>|a| \leq |\beta|</math>, όπου <math>a,\beta \in (V \cup T)^{*}</math> και επιτρέπεται <math>S \to \epsilon</math>. |
||
Στις γραμματικές '''τύπου 2''' ανήκουν οι [[ |
Στις γραμματικές '''τύπου 2''' ανήκουν οι [[Γραμματική χωρίς συμφραζόμενα|γραμματικές χωρίς συμφραζόμενα]] (context free grammar) και η μορφή των κανόνων παραγωγής τους είναι |
||
:<math>A \to a</math>, όπου <math>A \in V</math> και <math>a \in (V \cup T)^*</math>. |
:<math>A \to a</math>, όπου <math>A \in V</math> και <math>a \in (V \cup T)^*</math>. |
||
Έκδοση από την 19:16, 10 Ιουλίου 2008
To 1956 ο Νόαμ Τσόμσκι ταξινόμησε τις τυπικές γραμματικές σε ιεραρχία με κριτήριο τους τύπους των κανόνων παραγωγής τους.
Μια τυπική γλώσσα G αποτελείται από
- Ένα πεπερασμένο σύνολο V από μη τερματικά σύμβολα
- Ένα πεπερασμένο σύνολο Τ από τερματικά σύμβολα
- Ένα πεπερασμένο σύνολο P από κανόνες παραγωγής
- Ένα αρχικό σύμβολο S
όπου,
- .
Έτσι, μια τυπική γραμματική συμβολίζεται G(V,T,P,S).
Το επίπεδο ιεραρχίκας των γραμματικών μικραίνει καθώς προχωράμε από τον τύπο 0 ως 3. Σύμφωνα με την ιεραρχία του Τσόμσκι:
Στις γραμματικές τύπου 0 ανήκουν οι γενικές γραμματικές. Η μορφή των κανόνων παραγωγής είναι
- , όπου .
Στις γραμματικές τύπου 1 ανήκουν οι γραμματικές με συμφραζόμενα (context sensitive grammar) ή μονοτονικές γραμματικές (monotonic grammar). Η μορφή των κανόνων παραγωγής είναι
- , με , όπου και επιτρέπεται .
Στις γραμματικές τύπου 2 ανήκουν οι γραμματικές χωρίς συμφραζόμενα (context free grammar) και η μορφή των κανόνων παραγωγής τους είναι
- , όπου και .
Στις γραμματικές τύπου 3 ανήκουν οι κανονικές γραμματικές και η μορφή των κανόνων παραγωγής τους είναι δεξιογραμμικές (right-linear) ή αριστερογραμμικές (left-linear). Αν είναι δεξιογραμμικές, τότε
Ενώ, αν είναι αριστερογραμμική, τότε
- , όπου και .
Αυτό το λήμμα χρειάζεται επέκταση. Μπορείτε να βοηθήσετε την Βικιπαίδεια επεκτείνοντάς το. |