Ιεραρχία Τσόμσκι: Διαφορά μεταξύ των αναθεωρήσεων
Vevek (συζήτηση | συνεισφορές) μΧωρίς σύνοψη επεξεργασίας |
Vevek (συζήτηση | συνεισφορές) μΧωρίς σύνοψη επεξεργασίας |
||
Γραμμή 1: | Γραμμή 1: | ||
To [[1956]] ο [[Νόαμ Τσόμσκι]] ταξινόμησε τις [[τυπική γραμματική|τυπικές γραμματικές]] σε ιεραρχία με κριτήριο τους τύπους των κανόνων παραγωγής τους. |
To [[1956]] ο [[Νόαμ Τσόμσκι]] ταξινόμησε τις [[τυπική γραμματική|τυπικές γραμματικές]] σε ιεραρχία με κριτήριο τους τύπους των κανόνων παραγωγής τους. Κάτι πολύ χρήσιμο στην πεδίο της [[Επιστήμη υπολογιστών|Επιστήμης των υπολογιστών]]. |
||
==Τυπική γραμματική== |
==Τυπική γραμματική== |
Έκδοση από την 10:53, 11 Ιουλίου 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). Αν είναι δεξιογραμμικές, τότε
Ενώ, αν είναι αριστερογραμμική, τότε
- , όπου και .
Στις τύπου 3 γραμματικές, το πρώτο μέλος του κανόνα παραγωγής αποτελείται μόνο από μη τερματικά σύμβολα, ενώ το δεύτερο μέλος πρέπει να περιέχει και τερματικά σύμβολα.
Αυτό το λήμμα χρειάζεται επέκταση. Μπορείτε να βοηθήσετε την Βικιπαίδεια επεκτείνοντάς το. |