Μια προσπάθεια να διατυπώσει τη γραμματική μιας γλώσσας με μαθηματικούς όρους. Θεωρία γλώσσα είναι ένας σημαντικός τομέας της γλωσσολογίας και την επιστήμη υπολογιστών. Θεωρία τυπική γλώσσα κινήθηκε κατά τα μέσα της δεκαετίας του 1950, σε μια προσπάθεια να αναπτύξει θεωρίες για απόκτηση φυσικής γλώσσας. Αυτή θεωρία, και ειδικότερα το πλαίσιο χωρίς γραμματικές, βρέθηκε να σχετίζονται με τις γλώσσες που χρησιμοποιούνται στους υπολογιστές. Ενδιαφέρον για τη σχέση μεταξύ αφηρημένες γλώσσες και αυτόματα θεωρία ξεκίνησε με μια μελλοντοστραφείς χαρτί του S. , C. Κλέινι το 1956, στο οποίο αυτός χαρακτηρίζεται η ένταξη μιας πρότασης που θα μπορούσε να αποφασιστεί από μια μηχανή πεπερασμένων καταστάσεων γλώσσες. Τυπική ή αφηρημένα γλώσσες βασίζονται στην μαθηματική έννοια μιας γλώσσας όπως ορίζεται από τον Νόαμ Τσόμσκι περίπου 1956. Να κατανοήσουν την έννοια αυτή, μπορεί να αρχίσουμε ορίζοντας τι γλώσσα είναι. Το Νέο αμερικανικό λεξικό Oxford ορίζει ως «μέθοδος ανθρώπινης επικοινωνίας είτε προφορικό ή γραπτό, αποτελείται από τη χρήση των λέξεων σε μια δομημένη και συμβατικό τρόπο.» Ωστόσο, ο ορισμός αυτός είναι πολύ αόριστη για χρήση ως ένα δομικό στοιχείο μιας θεωρίας της γλώσσας. Να επισημοποιήσει την έννοια μιας αφηρημένης γλώσσας, είναι αναγκαίο να θεσπιστούν ορισμένοι Προκαταρκτικοί ορισμοί. Ένα αλφάβητο, λεξιλόγιο ή του συνόλου των τερματικών σταθμών, συμβολίζεται ως Σ, είναι οποιοδήποτε σύνολο πεπερασμένων, μη-κενό αδιαίρετα σύμβολα. Για παράδειγμα, το δυαδικό αρχείο αλφάβητο έχει μόνο δύο σύμβολα. Αυτό το σύνολο αντιπροσωπεύεται συνήθως ως Σ = (0, 1). A λέξη ή συμβολοσειρά, πάνω από ένα συγκεκριμένο αλφάβητο, είναι μια πεπερασμένη ακολουθία από σύμβολα του αλφαβήτου. Σε μαθηματικούς όρους, μια χαρακτηριστική λέξη, x, μπορεί να γραφεί ως x = α ₁, ₂, ₃,..., _k όπου k ≥ 0, μια ∊ Σ για 1 ≤ _μου μου ≤ k. Προσέξτε ότι εάν k = 0, το word ονομάζεται η λέξη null ή κενή λέξη και συμβολίζεται Λ. για παράδειγμα, χρησιμοποιώντας το δυαδικό αλφάβητο μπορεί να αποτελούμε οι λέξεις x = 0010 και y = 010. Δίνεται μια λέξη, x, ο αριθμός των εμφανίσεων συμβόλων από μια δεδομένη αλφάβητο της λέξης ονομάζεται το μήκος της λέξης και συμβολίζεται με