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