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

+ αυτόματα
(+ αυτόματα)
:<math>a \to \beta, a \neq \epsilon</math>, όπου <math>a,\beta \in (V \cup T)^{*}</math>.
Σε αυτήν την περίπτωση, οι [[συμβολοσειρά|συμβολοσειρές]] των κανόνων παραγωγής μπορούν να αποτελούνται από οποιαδήποτε σύμβολα της αλφαβήτου της γλώσσας.
 
Οι γενικές γραμματικές αναγνωρίζονται από τις [[Μηχανή Τούρινγκ|Μηχανές Τούρινγκ]] (Turing Machines).
 
===Γραμματικές Με Συμφραζόμενα===
:<math>A \to a</math>, όπου <math>A \in V</math> και <math>a \in (V \cup T)^*</math>.
Εδώ, η συμβολοσειρά Α δεν επιτρέπεται να περιέχει τερματικά σύμβολα, ενώ η α μπορεί να έχει οποιαδήποτε σύμβολα.
 
Τα αυτόματα που αναγνωρίζουν γραμματικές χωρις συμφαζόμενα είναι τα Αυτόματα Στοίβας (Push Down Automata).
 
===Κανονικές Γραμματικές===
:<math>A \to u, B \to Bu</math>, όπου <math>A,B \in V</math> και <math>u \in T^*</math>.
Στις τύπου 3 γραμματικές, το πρώτο μέλος του κανόνα παραγωγής αποτελείται μόνο από μη τερματικά σύμβολα, ενώ το δεύτερο μέλος πρέπει να περιέχει και τερματικά σύμβολα.
 
Τις κανονικές γραμματικές αναγνωρίζουν τα [[Πεπερασμένο Αυτόματο|Πεπερασμένα Αυτόματα]] ή Αναγνωριστές Πεπερασμένων Καταστάσεων (Finite State Acceptors).
 
 
435

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