Alphabets, mots et langages

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 $A$ un ensemble ; ses éléments seront appelés des symboles ; une suite finie $(a_1, \ldots, a_m)$ de symboles est appelée un mot sur l'alphabet $A$ ; un tel mot est aussi noté $a_1\ldots a_m$, et l'entier $m$ est sa longueur. L'ensemble de tous les mots sur l'alphabet $A$ est noté $A^\star$. Le produit (de concaténation) des mots $u=a_1\ldots a_m$ et $v=b_1\ldots b_n$ est le mot $uv = a_1\ldots a_m b_1\ldots b_n$, de longueur $m+n$. C'est une opération associative, pour laquelle le mot vide $\varepsilon$, de longueur nulle, est élément neutre.

Un langage d'alphabet $A$ est un sous-ensemble de $A^\star$. 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.