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

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

Στην επιστήμη υπολογιστών μια τυπική γραμματική (formal grammar)^[1] είναι μια αφηρημένη δομή που περιγράφει μια τυπική γλώσσα επακριβώς, δηλαδή είναι ένα σύνολο κανόνων που απεικονίζουν μαθηματικώς το σύνολο, (συνήθως απειροσύνολο), των πεπερασμένου μήκους στοιχειοσειρών / συμβολοσειρών που σχηματίζονται με διακριτά στοιχεία / σύμβολα (π.χ. γράμματα), τα οποία ανήκουν σε ένα σύνολο, συνήθως πεπερασμένο, που το λέμε αλφάβητο. Οι τυπικές γραμματικές ονομάστηκαν έτσι κατ’ αναλογία των γραμματικών των γλωσσών που μιλούν οι άνθρωποι, αλλά τα αλφάβητα τους δεν περιέχουν κατ’ ανάγκη γράμματα. Οι τυπικές γραμματικές διαχωρίζονται σε δυο κύριες κατηγορίες: γενετικές (generative) και αναλυτικές (analytic).

Μια γενετική γραμματική, (το πιο γνωστό είδος, που θα μπορούσε να ονομάζεται γεννητική ή παραγωγική γραμματική), είναι ένα σύνολο κανόνων με το οποίο όλες οι συμβολοσειρές που μπορούν να υπάρξουν σε μια γλώσσα μπορούν να παραχθούν με διαδοχικά επιθέματα ξεκινώντας από ένα προκαθορισμένο αρχικό σύμβολο δημιουργίας στοιχειοσειράς. Μια γενετική γραμματική ουσιαστικά είναι η τυπική μορφή του αλγορίθμου παραγωγής στοιχειοσειρών που ανήκουν στην γλώσσα.^[2]

Συνοπτικά για την γενετική γραμματική :

• λειτουργεί ως δημιουργός στοιχειοσειρών της γλώσσας, δηλαδή γράφει την γλώσσα,
• η πορεία είναι από την γραμματική προς τις λέξεις της γλώσσας,
• εφαρμόζεται παραγωγική (top-down) προσέγγιση, από το γενικό προς το μερικό.

Μια αναλυτική γραμματική, αντιθέτως, είναι ένα σύνολο κανόνων που υποθέτουν ότι μία αυθαίρετη στοιχειοσειρά δίνεται προς επεξεργασία και με διαδοχικά βήματα ανάλυσης προκύπτει ως αποτέλεσμα η τιμή μιας λογικής μεταβλητής:

• ΑΛΗΘΗΣ, αν η στοιχειοσειρά ανήκει στην γλώσσα που περιγράφει η αναλυτική γραμματική
• ΨΕΥΔΗΣ, αν η στοιχειοσειρά δεν ανήκει στην γλώσσα που περιγράφει η αναλυτική γραμματική.

Συνοπτικά για την αναλυτική γραμματική :

• σαρώνει την στοιχειοσειρά, τεχνολογεί τα μέρη που την αποτελούν και τα αναγνωρίζει, (είναι συντακτικός αναλυτής (parser)), δηλαδή διαβάζει την γλώσσα,
• η πορεία είναι από τις λέξεις της γλώσσας προς την γραμματική της,
• εφαρμόζεται επαγωγική (bottom-up) προσέγγιση, από το μερικό προς το γενικό.

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

Μια γενετική γραμματική συνίσταται από ένα σύνολο κανόνων για μετασχηματισμό στοιχειοσειρών. Για να δημιουργηθεί μια στοιχειοσειρά της γλώσσας, αρχίζουμε με μια στοιχειοσειρά που περιέχει μόνο το προκαθορισμένο αρχικό σύμβολο δημιουργίας στοιχειοσειράς, (συνήθως το '${\displaystyle S}$'), και εφαρμόζοντας διαδοχικά τους κανόνες (οσεσδήποτε φορές, με οποιαδήποτε σειρά) την τροποποιούμε. Η γλώσσα αποτελείται από όλες τις στοιχειοσειρές που μπορούν να δημιουργηθούν με αυτόν τον τρόπο.

Για παράδειγμα, υποθέτουμε ότι το αλφάβητο αποτελείται από '${\displaystyle a}$' και '${\displaystyle b}$', το σύμβολο έναρξης είναι '${\displaystyle S}$' και ισχύουν οι παρακάτω κανόνες (ή νόμοι) παραγωγής:

1. ${\displaystyle S\longrightarrow aSb}$

2. ${\displaystyle S\longrightarrow ba}$

και ξεκινάμε με την στοιχειοσειρά "${\displaystyle S}$", και μπορούμε να επιλέξουμε έναν κανόνα για να τον εφαρμόσουμε στην στοιχειοσειρά. Αν επιλέξουμε τον κανόνα 1, αντικαθιστούμε το '${\displaystyle S}$' με '${\displaystyle aSb}$' και παίρνουμε την "${\displaystyle aSb}$". Αν επιλέξουμε πάλι τον κανόνα 1, αντικαθιστούμε το '${\displaystyle S}$' με '${\displaystyle aSb}$' και παίρνουμε την "${\displaystyle aaSbb}$". Η διαδικασία συνεχίζεται μέχρι η στοιχειοσειρά να περιέχει μόνο στοιχεία από το αλφάβητο (δηλαδή '${\displaystyle a}$' και '${\displaystyle b}$'). Για να περαιωθεί το παράδειγμα, αν επιλέξουμε τώρα τον κανόνα 2, αντικαθιστούμε το '${\displaystyle S}$' με '${\displaystyle ba}$' και παίρνουμε την "${\displaystyle aababb}$", οπότε τελειώσαμε. Μπορούμε να γράψουμε αυτή την σειρά επιλογών πιο συνοπτικά, χρησιμοποιώντας σύμβολα : ${\displaystyle S\longrightarrow aSb\longrightarrow aaSbb\longrightarrow aababb}$. Η γλώσσα της γραμματικής είναι το σύνολο όλων των στοιχειοσειρών που μπορούν να παραχθούν με εφαρμογή αυτής της διαδικασίας : ${\displaystyle \left\{ba,abab,aababb,aaababbb,...\right\}}$.

Κάνοντας διάφορες επιλογές κανόνων κατά την διαδικασία δημιουργίας στοιχειοσειράς, παράγουμε μιά συγκεκριμένη στοιχειοσειρά. Αν αυτή η στοιχειοσειρά μπορεί να δημιουργηθεί και με διαφορετική σειρά επιλογών, τότε λέμε ότι η γραμματική είναι ασαφής ή ότι παράγει αμφισημίες. ^[3][4]

Τυπικός ορισμός

Στην κλασσική τυποποίηση των γενετικών γραμματικών, που πρώτος παρουσίασε ο Νόαμ Τσόμσκι το 1956, μια γραμματική G αποτελείται από τα παρακάτω μέρη:

• Ένα πεπερασμένο σύνολο ${\displaystyle N}$ μη–τελικών (nonterminal) συμβόλων.
• Ένα πεπερασμένο σύνολο ${\displaystyle \Sigma }$ τελικών (terminal) συμβόλων, το οποίο έχει τομή με το ${\displaystyle N}$ το κενό σύνολο.
• Ένα πεπερασμένο σύνολο ${\displaystyle P}$ κανόνων παραγωγής, όπου κάθε κανόνας έχει την μορφή

στοιχειοσειρά που ανήκει στο ${\displaystyle (\Sigma \cup N)^{*}\longrightarrow }$ στοιχειοσειρά που ανήκει στο ${\displaystyle (\Sigma \cup N)^{*}}$

(όπου ${\displaystyle {}^{*}}$ είναι Αστέρι Κλέινι και ${\displaystyle \cup }$ είναι ένωση συνόλων) με τον περιορισμό ότι η αριστερή πλευρά του κανόνα (δηλαδή το μέρος που βρίσκεται αριστερά από το ${\displaystyle \longrightarrow }$) πρέπει να περιέχει τουλάχιστον ένα μη–τελικό σύμβολο.

• Ένα σύμβολο ${\displaystyle S}$ που ανήκει στο ${\displaystyle N}$ και προσδιορίζεται ως αρχικό σύμβολο δημιουργίας στοιχειοσειράς (ή απλούστερα αρχικό σύμβολο).

Συνήθως, η τυπική γραμματική δηλώνεται ως μια διατεταγμένη τετράδα

${\displaystyle G}$ = ${\displaystyle (N,\Sigma ,P,S)}$.

Η γλώσσα μιας τυπικής γραμματικής ${\displaystyle G=(N,\Sigma ,P,S)}$, που συμβολίζεται ${\displaystyle {\boldsymbol {L}}(G)}$, ορίζεται ως το σύνολο όλων των στοιχειοσειρών του ${\displaystyle \Sigma }$ που μπορούν να παραχθούν ξεκινώντας από μια στοιχειοσειρά με περιεχόμενο το αρχικό σύμβολο ${\displaystyle S}$ και εφαρμόζοντας επαναληπτικά στην στοιχειοσειρά τους κανόνες παραγωγής του ${\displaystyle P}$ μέχρι να μη περιέχει η στοιχειοσειρά μη–τελικά σύμβολα.

Παράδειγμα

Για τα παραδείγματα αυτά, τα σχετικά με τις τυπικές γλώσσες σύνολα καθορίζονται με τον συμβολισμό δόμησης συνόλου.

Θεωρούμε, για παράδειγμα, την γραμματική ${\displaystyle G1}$ με ${\displaystyle N=\left\{S,B\right\}}$, ${\displaystyle \Sigma =\left\{a,b,c\right\}}$, το ${\displaystyle P}$ να απαρτίζεται από τους ακόλουθους κανόνες παραγωγής

1. ${\displaystyle S\longrightarrow aBSc}$

2. ${\displaystyle S\longrightarrow abc}$

3. ${\displaystyle Ba\longrightarrow aB}$

4. ${\displaystyle Bb\longrightarrow bb}$

και το μη–τελικό σύμβολο ${\displaystyle S}$ ως αρχικό σύμβολο. Μερικά δείγματα παραγωγής στοιχειοσειρών της γλώσσας ${\displaystyle {\boldsymbol {L}}(G1)}$ ακολουθούν, (και σημειώνουμε σε παρένθεση τον αριθμό του κανόνα που χρησιμοποιείται, και με έντονη γραφή το τμήμα της στοιχειοσειράς που αντικαθίσταται):

• ${\displaystyle {\boldsymbol {S}}\longrightarrow (2)abc}$
• ${\displaystyle {\boldsymbol {S}}\longrightarrow (1)aB{\boldsymbol {S}}c\longrightarrow (2)a{\boldsymbol {Ba}}bcc\longrightarrow (3)aa{\boldsymbol {Bb}}cc\longrightarrow (4)aabbcc}$
• ${\displaystyle {\boldsymbol {S}}\longrightarrow (1)aB{\boldsymbol {S}}c\longrightarrow (1)aBaB{\boldsymbol {S}}cc\longrightarrow (2)a{\boldsymbol {Ba}}Babccc}$ ${\displaystyle \longrightarrow (3)aaB{\boldsymbol {Ba}}bccc\longrightarrow (3)aa{\boldsymbol {Ba}}Bbccc\longrightarrow (3)aaaB{\boldsymbol {Bb}}ccc}$ ${\displaystyle \longrightarrow (4)aaa{\boldsymbol {Bb}}bccc\longrightarrow (4)aaabbbccc}$

Είναι φανερό ότι αυτή η γραμματική ορίζει την γλώσσα, (έστω ότι την ονομάζουμε γλώσσα-1), ${\displaystyle \left\{a^{n}b^{n}c^{n}|n>0\right\}}$, όπου ${\displaystyle a^{n}}$ είναι μια στοιχειοσειρά μήκους n αποτελούμενη από χαρακτήρες ${\displaystyle a}$. Επομένως, η πλήρης γλώσσα συνίσταται από στοιχειοσειρές που έχουν στην αρχή τους ένα θετικό πλήθος από χαρακτήρες 'a', ακολουθούμενο από ίσο πλήθος χαρακτήρων 'b', ακολουθούμενο από ίσο πλήθος χαρακτήρων 'c'.

Συστήματα-L

Οι τυπικές γενετικές γραμματικές είναι παρόμοιες με τα συστήματα-L (συστήματα Lindenmayer)^[5], με τις εξής διαφορές:

• τα συστήματα-L δεν έχουν διάκριση μεταξύ τελικών και μη–τελικών συμβόλων,
• τα συστήματα-L έχουν περιορισμούς στην σειρά εφαρμογής των κανόνων,
• τα συστήματα-L δεν έχουν πέρας εφαρμογής των κανόνων, και δημιουργούν μια άπειρη ακολουθία στοιχειοσειρών.

Τυπικά, κάθε στοιχειοσειρά σχετίζεται με ένα σύνολο σημείων του χώρου, και το εξαγόμενο ενός συστήματος-L ορίζεται ότι είναι το όριο αυτών των συνόλων.

Η Ιεραρχία του Τσόμσκι

Κύριο λήμμα: Ιεραρχία Τσόμσκι

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

Δυο σημαντικοί τύποι είναι η Γραμματική χωρίς συμφραζόμενα (context-free grammar) και η Κανονική γραμματική (regular grammar), και οι γλώσσες που παράγονται από τέτοιες γραμματικές ονομάζονται αντίστοιχα Γλώσσα χωρίς συμφραζόμενα και Κανονική γλώσσα. Αν και δεν είναι τόσο δυνατές γραμματικές, όσο είναι η απεριόριστη γραμματική (unrestricted grammar) που μπορεί να εκφράσει οποιαδήποτε γλώσσα μπορεί να γίνει αποδεκτή από μια Μηχανή Τούρινγκ (Turing machine), αυτοί οι δυο τύποι περιορισμένων γραμματικών χρησιμοποιούνται πολύ συχνά επειδή μπορούν να δημιουργηθούν εύκολα συντακτικοί αναλυτές γι’ αυτές. Πράγματι, για τις γραμματικές χωρίς συμφραζόμενα υπάρχουν πολύ γνωστοί αλγόριθμοι για την δημιουργία αποδοτικών συντακτικών αναλυτών, που είναι γραμμικοί από αριστερά ή από δεξιά.

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

Σε μια Γραμματική χωρίς συμφραζόμενα, το αριστερό μέρος κάθε κανόνα παραγωγής περιέχει μόνο ένα μη–τελικό σύμβολο. Η γλώσσα-1 που ορίστηκε προηγουμένως δεν είναι «Γλώσσα χωρίς συμφραζόμενα», αλλά η επόμενη είναι:

Είναι «Γλώσσα χωρίς συμφραζόμενα» η γλώσσα, (έστω ότι την ονομάζουμε γλώσσα-2), ${\displaystyle \left\{a^{n}b^{n}|n>0\right\}}$ (οποιοδήποτε θετικό πλήθος χαρακτήρων 'a', ακολουθούμενο από ίσο πλήθος χαρακτήρων 'b'), που ορίζεται με την γραμματική ${\displaystyle G2}$ που έχει ${\displaystyle N=\left\{S\right\}}$, ${\displaystyle \Sigma =\left\{a,b\right\}}$, αρχικό σύμβολο ${\displaystyle S}$, και τους παρακάτω κανόνες παραγωγής:

1. ${\displaystyle S\longrightarrow aSb}$

2. ${\displaystyle S\longrightarrow ab}$

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

Σε μια Κανονική γραμματική, το αριστερό μέρος κάθε κανόνα παραγωγής περιέχει μόνο ένα μη–τελικό σύμβολο, αλλά και το δεξιό μέρος του κανόνα έχει περιορισμό: Επιτρέπεται να είναι κενό, ή να περιέχει μόνο ένα μη–τελικό σύμβολο, ή να περιέχει μόνο ένα τελικό σύμβολο ακολουθούμενο από ένα μη–τελικό σύμβολο. (Ενίοτε χρησιμοποιείται ένας ευρύτερος ορισμός: επιτρέπονται μακρύτερες στοιχειοσειρές τελικών συμβόλων ή μόνο μη–τελικά σύμβολα, ώστε να είναι ευκολότερη η περιγραφή της γλώσσας, χωρίς να αλλάζει ο τύπος της γλώσσας). Η γλώσσα-2 που ορίσαμε προηγουμένως δεν είναι κανονική, αλλά η επόμενη είναι:

Είναι «Κανονική γλώσσα» η γλώσσα, (έστω ότι την ονομάζουμε γλώσσα-3), ${\displaystyle \left\{a^{n}b^{m}|m,n>0\right\}}$ (οποιοδήποτε θετικό πλήθος χαρακτήρων 'a', ακολουθούμενο από οποιοδήποτε θετικό πλήθος χαρακτήρων 'b', όπου τα δύο πλήθη μπορεί να διαφέρουν), καθώς μπορεί να οριστεί από την γραμματική ${\displaystyle G3}$ με ${\displaystyle N=\left\{S,A,B\right\}}$, ${\displaystyle \Sigma =\left\{a,b\right\}}$, αρχικό σύμβολο ${\displaystyle S}$, και τους ακόλουθους κανόνες παραγωγής:

1. ${\displaystyle S\longrightarrow aA}$

2. ${\displaystyle A\longrightarrow aA}$

3. ${\displaystyle A\longrightarrow bB}$

4. ${\displaystyle B\longrightarrow bB}$

5. ${\displaystyle B\longrightarrow \epsilon }$

(όπου ${\displaystyle \epsilon }$ συμβολίζει την κενή στοιχειοσειρά, δηλαδή μια στοιχειοσειρά με μήκος μηδενικό).

Πρακτικά, οι κανονικές γραμματικές συνήθως ορίζονται με κανονικές εκφράσεις.

Σύγκριση Κανονικής γλώσσας με Γλώσσα χωρίς συμφραζόμενα

Πέρα από τις διαφορές στους κανόνες παραγωγής, που απαιτούνται για να παραχθούν οι δυο τύποι γλωσσών, η ουσιαστική διαφορά μεταξύ της χωρίς συμφραζόμενα γλώσσας-2

${\displaystyle \left\{a^{n}b^{n}|n>0\right\}}$

και της κανονικής γλώσσας-3

${\displaystyle \left\{a^{n}b^{m}|n,m>0\right\}}$

είναι η προδιαγραφή ότι το πλήθος των χαρακτήρων 'a' πρέπει να είναι ίσο με το πλήθος των χαρακτήρων 'b' στην χωρίς συμφραζόμενα γλώσσα-2. Επομένως, οποιοδήποτε αυτόματο που θα προσπαθήσει να αναλύσει συντακτικά τις στοιχειοσειρές της γλώσσας χωρίς συμφραζόμενα πρέπει κατ’ ανάγκη να κρατάει λογαριασμό για περισσότερες πληροφορίες από εκείνο το αυτόματο που θα αναλύσει συντακτικά την κανονική γλώσσα. Το τελευταίο δεν χρειάζεται να μετρήσει το πλήθος των 'a' και των 'b', αλλά το μόνο που απαιτείται είναι να βεβαιώσει ότι το πλήθος καθενός δεν είναι μηδενικό.

Για περισσότερες λεπτομέρειες, δείτε Γλώσσα χωρίς συμφραζόμενα και Κανονική γλώσσα.

Άλλοι τύποι γενετικών γραμματικών

Πολλές επεκτάσεις και παραλλαγές της πρωτότυπης ιεράρχησης, (Ιεραρχία Τσόμσκι), των τυπικών γραμματικών έχουν πρόσφατα αναπτυχθεί, και από γλωσσολόγους και από πληροφορικούς, είτε για αυξήσουν την εκφραστική ισχύ των γραμματικών, είτε για να τις κάνουν προσιτές σε συντακτική (ή άλλη) ανάλυση. Βέβαια αυτοί οι δυο στόχοι είναι αντιδιαμετρικοί : όσο περισσότερο εκφραστική είναι μια τυπική γραμματική, τόσο δυσκολότερο είναι να αναλυθεί, συντακτικά ή αλλιώς, με αυτοματοποιημένες μεθόδους. Μερικοί τύποι γραμματικών, που έχουν αναπτυχθεί πρόσφατα, είναι:

• Η Γραμματική προσάρτησης δένδρων (Tree-adjoining grammar) αυξάνει την εκφραστικότητα της συμβατικής γενετικής γραμματικής με το να επιτρέπει στους κανόνες παραγωγής να επενεργούν σε δένδρα συντακτικής ανάλυσης και όχι μόνο σε στοιχειοσειρές.
• Η Γραμματική παραθημάτων (Affix grammar) και η Γραμματική ιδιοτήτων (attribute grammar) επιτρέπουν την επαύξηση των παραγωγικών κανόνων με σημασιολογικές ιδιότητες και λειτουργίες, και είναι και οι δύο χρήσιμες στην αύξηση της εκφραστικότητας της γραμματικής και στην κατασκευή εύχρηστων εργαλείων μετάφρασης γλωσσών.

Ένα ετήσιο συνέδριο Αρχειοθετήθηκε 2007-10-08 στο Wayback Machine. είναι αφιερωμένο στις τυπικές γραμματικές.

Αναλυτικές γραμματικές

Αν και υπάρχει τεράστιο πλήθος δημοσιεύσεων για αλγορίθμους συντακτικών αναλυτών, οι πλείστοι των αλγορίθμων αυτών θεωρούν ότι η γλώσσα που πρόκειται να αναλυθεί συντακτικά πρέπει αρχικά να περιγραφεί με μια γενετική τυπική γραμματική, και ότι ο στόχος είναι να μετασχηματιστεί αυτή η γενετική γραμματική σε έναν λειτουργικό συντακτικό αναλυτή. Η εναλλακτική προσέγγιση είναι να τυποποιηθεί αρχικά η γλώσσα μέσω μιας αναλυτικής γραμματικής, η οποία έχει αμεσότερη αντιστοιχία με την δομή ενός συντακτικού αναλυτή της γλώσσας αυτής. Ακολουθούν παραδείγματα τυποποιήσεων με αναλυτικές γραμματικές:

• Η γλωσσομηχανή (The Language Machine) εφαρμόζει άμεσα απεριόριστες αναλυτικές γραμματικές. Χρησιμοποιούνται κανόνες αντικατάστασης για τον μετασχηματισμό μιας εισόδου σε εξόδους και συμπεριφορές. Το σύστημα μπορεί επίσης να παραγάγει το διάγραμμα-lm (the lm-diagram) που δείχνει τι συμβαίνει όταν εφαρμόζονται οι κανόνες της απεριόριστης αναλυτικής γραμματικής.
• Γλώσσα παραγωγικής συντακτικής ανάλυσης (Top-down parsing language, TDPL) : ένας εξαιρετικά μινιμαλιστικός φορμαλισμός αναλυτικών γραμματικών που αναπτύχθηκε στην αρχή της δεκαετίας 1970 για την μελέτη των παραγωγικών (top-down) συντακτικών αναλυτών (parser).
• Γραμματική συντακτικής ανάλυσης εκφράσεων (Parsing expression grammar, PEG) : μια πρόσφατη γενίκευση της TDPL σχεδιασμένη να αντιμετωπίσει τις ανάγκες εκφραστικότητας (expressiveness) για συγγραφείς γλωσσών προγραμματισμού και συμβολομεταφραστών.
• Γραμματική σύνδεσης (Link grammar) : μια μορφή αναλυτικής γραμματικής, σχεδιασμένη για την Γλωσσολογία, που εξετάζει τις σχέσεις θέσεων σε ζεύγη λέξεων και παράγει συντακτική δομή.

Δείτε επίσης

• Δένδρο συντακτικής ανάλυσης (Parse tree)
• Δένδρο αφηρημένης σύνταξης (Abstract syntax tree)
• Ασαφής γραμματική (ambiguous grammar)

Πηγές

• Το άρθρο είναι μεταφορά στα ελληνικά του άρθρου w:en:Formal grammar της αγγλικής Βικιπαίδειας.

Θεωρία αυτομάτων: τυπικές γλώσσες και τυπικές γραμματικές
Ιεραρχία Τσόμσκι	Γραμματικές	Γλώσσες	Ελάχιστο αυτόματο
Τύπος-0	Απεριόριστες	Αναδρομικά αριθμήσιμη	Μηχανή Τούρινγκ
-	(χωρίς κοινό όνομα)	Αναδρομική	Αποφασιστής
Τύπος-1	Με συμφραζόμενα	Με συμφραζόμενα	Γραμμικό φραγμένο
Τύπος-2	Χωρίς συμφραζόμενα	Χωρίς συμφραζόμενα	Σωρού
Τύπος-3	Κανονική	Κανονική	Πεπερασμένο
Κάθε κατηγορία γλώσσας ή γραμματικής είναι γνήσιο υποσύνολο της κατηγορίας που είναι ακριβώς από πάνω της.

Παραπομπές

1. «Τυπική γραμματική, the Glossary». el.unionpedia.org. Ανακτήθηκε στις 31 Οκτωβρίου 2023. 
2. Meduna, Alexander (2014), Formal Languages and Computation: Models and Their Applications, CRC Press, σελ. 233, ISBN 9781466513457, https://books.google.com/books?id=KJ-NAgAAQBAJ&pg=PA233 . For more on this subject, see undecidable problem.
3. Ginsburg, Seymour (1975). Algebraic and automata theoretic properties of formal languages. North-Holland. σελίδες 8–9. ISBN 978-0-7204-2506-2. 
4. Harrison, Michael A. (1978). Introduction to Formal Language Theory. Reading, Mass.: Addison-Wesley Publishing Company. σελίδες 13. ISBN 978-0-201-02955-0. 
5. «Συμβολή των L-συστημάτων στην αλγοριθμική περιγραφή και μοντελοποίηση πολύπλοκων οργανικών δομών».