L'étude des langues formelles concerne la définition, la description (génération) et l'analyse (reconnaissance) d'ensembles de chaînes sur des ensembles de symboles finis. L'ensemble de toutes les représentations binaires des entiers, l'ensemble de tous les palindromes sur l'alphabet latin minuscule et l'ensemble de toutes les représentations binaires de machines de Turing qui n'acceptent pas eux-mêmes sont des exemples de langues formelles.
