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

Στις γραμματικές '''τύπου 2''' ανήκουν οι [[Γραμματική χωρίς συμφραζόμενα|γραμματικές χωρίς συμφραζόμενα]] (context free grammar) και η μορφή των κανόνων παραγωγής τους είναι
:<math>A \to a</math>, όπου <math>A \in V</math> και <math>a \in (V \cup T)^*</math>.
Εδώ, το Α δεν είναι συμβολοσειρά, αλλά ένα μη τερματικό σύμβολο, ενώ το α είναι συμβολοσειρά αποτελούμενη από οποιαδήποτε σύμβολα της αλφαβήτου της γλώσσας. Από ένα μη τερματικό σύμβολο παράγεται οποιαδήποτε συμβολοσειρά.
Εδώ, η συμβολοσειρά Α δεν επιτρέπεται να περιέχει τερματικά σύμβολα, ενώ η α μπορεί να έχει οποιαδήποτε σύμβολα.
 
Τα αυτόματα που αναγνωρίζουν γραμματικές χωρις συμφαζόμενα είναι τα [[Αυτόματο Στοίβας|Αυτόματα Στοίβας]] (Push Down Automata).
435

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