Ιεραρχία Τσόμσκι: Διαφορά μεταξύ των αναθεωρήσεων
Χωρίς σύνοψη επεξεργασίας |
μ To "Ιεραρχία του Τσόμσκι" μετακινήθηκε στο "Ιεραρχία Τσόμσκι" |
(Καμία διαφορά)
|
Έκδοση από την 19:17, 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). Αν είναι δεξιογραμμικές, τότε
Ενώ, αν είναι αριστερογραμμική, τότε
- , όπου και .
Αυτό το λήμμα χρειάζεται επέκταση. Μπορείτε να βοηθήσετε την Βικιπαίδεια επεκτείνοντάς το. |