Expressions rationnelles

Le produit de concaténation des mots s'étend naturellement aux langages : si $X$ et $Y$ sont des langages d'alphabet $A$, le produit $XY$ est l'ensemble des mots $uv$ tels que $u\in X$ et $v\in Y$. On définit aussi les puissances, l'étoile et l'étoile propre d'un langage :

$$X^{0}=\{ \varepsilon \}, \quad X^{n+1}=X^{n}X, \mathrm{pour}... ..._{n \geq 0} X^{n}, \quad X^{+}=\bigcup\limits_{n \geq 1} X^{n}$$

Les langages d'alphabet $A$, en tant que sous-ensembles de $A^\star$, peuvent aussi être combinés par les opérations ensemblistes : union, intersection, complémentation.

On dit qu'un langage est rationnel s'il peut être obtenu à partir des langages singletons (à un seul mot) par un nombre fini d'unions, de produits et d'étoiles. Par exemple $\{a\}^\star\{b\}\{b\}(\{a\}\cup\{b\})^\star$ est un langage rationnel formé des mots commençant par un nombre quelconque de $a$, suivi de deux occurrences de $b$ et se terminant par un nombre quelconque de $a$ et de $b$. Ce langage peut être défini au moyen de l'expression rationnelle $a^\star bb(a\vert b)^\star$.

Une telle expression est un objet formel, dont la valeur est un langage, de même que la valeur d'une expression arithmétique est un nombre. Les expressions rationnelles (ou régulières, parfois dénommées en anglais informatique regexp) sont largement utilisées à la fois dans les fonctions de recherche des éditeurs de texte et dans l'environnement Unix. Ainsi, la commande egrep exp f d'Unix recherche toutes les lignes d'un fichier f contenant une chaîne de caractères appartenant au langage valeur de l'expression rationnelle exp.

Par exemple, les chaînes de caractères représentant un identificateur valide en C++ (et dans la plupart des langages de programmation) forment un langage rationnel sur l'alphabet ASCII. Les langages de ce type sont considérés comme les langages les plus simples, après les langages finis. On dispose ainsi, avec la notion d'expression rationnelle, d'un moyen formel pour définir certains langages. Cependant, ces expressions ne donnent pas directement d'algorithme résolvant le problème d'appartenance d'un mot à un langage d'expression rationnelle donnée. Les automates finis résoudront ce problème.