Un langage est un ensemble de mots, un mot est une suite finie de symboles, un symbole est un élément d'un alphabet, et un alphabet est un ensemble quelconque, de préférence fini. Quand on s'intéresse à des textes, on travaille avec un alphabet formé d'un jeu de caractères (par exemple l'alphabet ASCII à 128 caractères, ou l'une de ses extensions comme l'alphabet iso-latin1 à 256 caractères), mais toutes sortes d'alphabets sont aussi utilisées dans la pratique.
Autrement dit, soit un ensemble ; ses éléments seront appelés des
symboles ; une suite finie
de symboles est
appelée un mot sur l'alphabet
; un tel mot est aussi
noté
, et l'entier
est sa longueur.
L'ensemble de tous les mots sur l'alphabet
est noté
. Le
produit (de concaténation) des mots
et
est le mot
, de longueur
. C'est une opération associative, pour
laquelle le mot vide
, de longueur nulle, est élément
neutre.
Un langage d'alphabet est un sous-ensemble de
. Un
des problèmes classiques de l'informatique consiste à décider si un mot
appartient à un langage donné : par exemple, telle suite de caractères
ASCII est-elle un programme C++ ? Au préalable, il faut avoir adopté une
définition précise du langage considéré. On trouvera en appendice la
définition du langage C++ à l'aide d'un ensemble de règles de grammaire ;
celles-ci sont utilisées pour construire la partie du compilateur
qui est capable de répondre à cette question, en signalant également les
erreurs de grammaire. Il existe aussi des langages tels qu'aucun
algorithme ne permet de répondre à cette question.