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$. Un important résultat de la théorie des langages est dû à Kleene  (1956) : un langage est reconnaissable par un automate fini si et seulement s'il est rationnel. Par exemple, le langage défini par l'expression rationnelle $a^\star bb(a\vert b)^\star$ est reconnu par l'automate déterministe de la figure 2.26. C'est ainsi que sont réalisées les opérations de recherche de la commande egrep d'Unix.

 

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 de 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 Java (et dans la plupart des langages de programmation) forment un langage rationnel sur l'alphabet Unicode. 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.