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

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
Lady 6thofAu (συζήτηση | συνεισφορές)
Vevek (συζήτηση | συνεισφορές)
Γραμμή 26: Γραμμή 26:
Στις γραμματικές '''τύπου 1''' ανήκουν οι [[Γραμματική με συμφραζόμενα|γραμματικές με συμφραζόμενα]] (context sensitive grammar) ή μονοτονικές γραμματικές (monotonic grammar). Η μορφή των κανόνων παραγωγής είναι
Στις γραμματικές '''τύπου 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>.
Και πάλι οι συμβολοσειρές α και β μπορούν να αποτελούνται από οποιαδήποτε σύμβολα της αλφαβήτου, αλλά πρέπει το μήκος της συμβολοσειράς α να είναι μικρότερο ή ίσο από αυτό της β.
Και πάλι οι συμβολοσειρές α και β μπορούν να αποτελούνται από οποιαδήποτε σύμβολα της αλφαβήτου, αλλά πρέπει το μήκος της συμβολοσειράς α να είναι μικρότερο ή ίσο από αυτό της β, γι'αυτό άλλωστε οι γλώσσες αυτές ονομάζονται μονοτονικές.

Τα αυτόματα που αναγνωρίζουν γραμματικές χωρίς συμφραζόμενα είναι τα [[Γραμμικά Περιορισμένο Αυτόματο|Γραμμικά Περιορισμένα Αυτόματα]] (Linearly Bounded Automata).


===Γραμματικές Χωρίς Συμφραζόμενα===
===Γραμματικές Χωρίς Συμφραζόμενα===

Έκδοση από την 22:55, 4 Οκτωβρίου 2008

To 1956 ο Νόαμ Τσόμσκι ταξινόμησε τις τυπικές γραμματικές σε ιεραρχία με κριτήριο τους τύπους των κανόνων παραγωγής τους. Η ιεραρχία Τσόμσκι, όπως ονομάστηκε, θεωρείται πολύ χρήσιμη στο πεδίο της Επιστήμης των υπολογιστών.

Τυπική γραμματική

Κύριο λήμμα: Τυπική γραμματική

Μια τυπική γλώσσα G αποτελείται από

  • Ένα πεπερασμένο σύνολο V από μη τερματικά σύμβολα
  • Ένα πεπερασμένο σύνολο Τ από τερματικά σύμβολα
  • Ένα πεπερασμένο σύνολο P από κανόνες παραγωγής
  • Ένα αρχικό σύμβολο S

όπου,

  • .

Έτσι, μια τυπική γραμματική συμβολίζεται G(V,T,P,S).

Ιεραρχία Τσόμσκι

Το επίπεδο ιεραρχίας των γραμματικών χαμηλώνει καθώς προχωράμε από τον τύπο 0 ως 3. Σύμφωνα με την ιεραρχία του Τσόμσκι:

Γενικές Γραμματικές

Στις γραμματικές τύπου 0 ανήκουν οι γενικές γραμματικές. Η μορφή των κανόνων παραγωγής είναι

, όπου .

Σε αυτήν την περίπτωση, οι συμβολοσειρές των κανόνων παραγωγής μπορούν να αποτελούνται από οποιαδήποτε σύμβολα της αλφαβήτου της γλώσσας.

Γραμματικές Με Συμφραζόμενα

Στις γραμματικές τύπου 1 ανήκουν οι γραμματικές με συμφραζόμενα (context sensitive grammar) ή μονοτονικές γραμματικές (monotonic grammar). Η μορφή των κανόνων παραγωγής είναι

, με , όπου και επιτρέπεται .

Και πάλι οι συμβολοσειρές α και β μπορούν να αποτελούνται από οποιαδήποτε σύμβολα της αλφαβήτου, αλλά πρέπει το μήκος της συμβολοσειράς α να είναι μικρότερο ή ίσο από αυτό της β, γι'αυτό άλλωστε οι γλώσσες αυτές ονομάζονται μονοτονικές.

Τα αυτόματα που αναγνωρίζουν γραμματικές χωρίς συμφραζόμενα είναι τα Γραμμικά Περιορισμένα Αυτόματα (Linearly Bounded Automata).

Γραμματικές Χωρίς Συμφραζόμενα

Στις γραμματικές τύπου 2 ανήκουν οι γραμματικές χωρίς συμφραζόμενα (context free grammar) και η μορφή των κανόνων παραγωγής τους είναι

, όπου και .

Εδώ, η συμβολοσειρά Α δεν επιτρέπεται να περιέχει τερματικά σύμβολα, ενώ η α μπορεί να έχει οποιαδήποτε σύμβολα.

Κανονικές Γραμματικές

Στις γραμματικές τύπου 3 ανήκουν οι κανονικές γραμματικές και η μορφή των κανόνων παραγωγής τους είναι δεξιογραμμικές (right-linear) ή αριστερογραμμικές (left-linear). Αν είναι δεξιογραμμικές, τότε

Ενώ, αν είναι αριστερογραμμική, τότε

, όπου και .

Στις τύπου 3 γραμματικές, το πρώτο μέλος του κανόνα παραγωγής αποτελείται μόνο από μη τερματικά σύμβολα, ενώ το δεύτερο μέλος πρέπει να περιέχει και τερματικά σύμβολα.