Στα διακριτά μαθηματικά, στη μαθηματική λογική και στη θεωρητική πληροφορική, μια τυπική γλώσσα (formal language) ή απλώς γλώσσα είναι η γλώσσα που ορίζεται από ακριβείς μαθηματικούς τύπους, ή τύπους που μπορεί να επεξεργαστεί μια μηχανή. Πιο αναλυτικά, μια γλώσσα {L}ορίζεται ως ένα πιθανώς άπειρο σύνολο από πεπερασμένου μήκους σειρές από στοιχεία προερχόμενα από ένα καθορισμένο, πεπερασμένο σύνολο{A} (αλφάβητο). Ο κλάδος που μελετά τις ιδιότητες των τυπικών γλωσσών λέγεται θεωρία τυπικών γλωσσών.

Όπως και οι γλώσσες στη γλωσσολογία, οι τυπικές γλώσσες έχουν γενικά δυο πλευρές:

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

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

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

Θεωρήστε ένα απλό παράδειγμα, το αλφάβητο {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, =}, και τους ακόλουθους συντακτικούς κανόνες:

  • Κάθε συμβολοσειρά που δεν περιέχει + ή = και δεν αρχίζει με 0 ανήκει στη γλώσσα.
  • Η συμβολοσειρά που αποτελείται από το σύμβολο 0 ανήκει στη γλώσσα.
  • Μια συμβολοσειρά που περιέχει το = ανήκει στη γλώσσα, αν και μόνον αν υπάρχει ακριβώς ένα = το οποίο τη χωρίζει σε δυο συμβολοσειρές, που ανήκουν στη γλώσσα.
  • Οποιοσδήποτε αριθμός συμβόλων + μπορούν να υπάρχουν σε μια συμβολοσειρά, αρκεί να περιβάλλονται από σύμβολα διαφορετικά από + και =.
  • Δεν ανήκουν άλλες συμβολοσειρές στη γλώσσα εκτός από αυτές που ικανοποιούν τους παραπάνω κανόνες.
Υπό αυτούς τους κανόνες, η συμβολοσειρά "23+4=555" ανήκει στη γλώσσα, ενώ η συμβολοσειρά "-234=+" δεν ανήκει. Η τυπική γλώσσα αυτή περιγράφει αριθμούς, καλώς ορισμένες εκφράσεις πρόσθεσης, και καλώς ορισμένες εξισώσεις προσθέσεων, αλλά εκφράζει μόνο το πως φαίνονται (το συντακτικό τους), και όχι το τι σημαίνουν (τη σημασιολογία ή σημαντική τους). Για παράδειγμα, δεν ορίζεται πουθενά στους παραπάνω κανόνες ότι το σύμβολο 0 σημαίνει τον αριθμό μηδέν ή ότι το σύμβολο + σημαίνει πρόσθεση.

Πράξεις 

Για παράδειγμα, αν L1 και L2 είναι γλώσσες που ορίζονται πάνω σε ένα κοινό αλφάβητο, τότε:

  1. Η συνένωση (concatenation) L1 και L2 αποτελείται από όλες τις συμβολοσειρές μορφής vw όπου η v είναι συμβολοσειρά της L1 και η w είναι συμβολοσειρά τηςL2
  2. Η τομή (intersection) L1∩L2 των L1 και L2 αποτελείται από όλες τις συμβολοσειρές που ανήκουν και στις δύο γλώσσες.
  3. Η ένωση (union) L1∪L2 της L1 με την L2 αποτελείται από όλες τις συμβολοσειρές που περιέχονται στην L1 ή στηνL2.
  4. Το συμπλήρωμα (complement) της γλώσσας L1 αποτελείται από όλες τις συμβολοσειρές που σχηματίζονται από το αλφάβητο της γλώσσας, αλλά δεν περιέχονται στην L1.
  5. Το δεξιό πηλίκο (right quotient) L1/L2 της L1 δια της L2 αποτελείται από όλες τις συμβολοσειρές v για τις οποίες υπάρχει μια συμβολοσειρά w στην L2 τέτοια ώστε η συνένωση vw να περιέχεται στην L1.
  6. Το Άστρο του Κλήνυ (Kleene star) L^* αποτελείται από όλες τις συμβολοσειρές που μπορούν να γραφούν στην μορφή w1w2 ... wn, όπου οι συμβολοσειρές wi  περιέχονται στην L και n ≥ 0. Περιλαμβάνεται και η κενή συμβολοσειρά ε επειδή επιτρέπεται το n = 0.
  7. Το αντίστροφο L1^R περιέχει τις αντίστροφες (παλίνδρομες, καρκινικές) μορφές όλων των συμβολοσειρών της L1.
  8. Το ανακάτεμα των L1 και L2 απαρτίζεται από όλες τις συμβολοσειρές που μπορούν να γραφούν στην μορφή v1w1v2w2 ... vnwn όπου n≥ 1 και οι v1 ... ,vn είναι συμβολοσειρές που η συνένωσή τους τους v1 ... vn περιέχεται στην L1 και οι w1, ... ,wn  είναι συμβολοσειρές που η συνένωσή τους w1 ... wn περιέχεται στην L2.

Παραδείγματα Τυπικών Γλωσσών

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

Το αλφάβητο έστω ότι είναι το { a , b }. Παραδείγματα γλωσσών τότε είναι:
  • το σύνολο όλων των συμβολοσειρών που σχηματίζονται από {a, b}  L ={ w ∈Σ^*}
  • το σύνολο { a^n}, όπου n είναι πρώτος αριθμός και a^n σημαίνει σειρά χαρακτήρων a που είναι n στο πλήθος
  •  L = { w ∈Σ^*|  w αποτελείται από  n  πλήθος  a , όπου  n  πρώτος αριθμός}
  • πεπερασμένες γλώσσες, όπως η  L = {a, aa, bba}
ή επίσης γενικότερα παραδείγματα:
  • το σύνολο των συντακτικά σωστών προγραμμάτων σε δεδομένη γλώσσα προγραμματισμού
  • το σύνολο των εισόδων για τις οποίες μια δεδομένη μηχανή Τούρινγκ σταματά.