✖

Expressions régulières

Une expression régulière est une chaîne de caractères qui permet de décrire un ensemble de mots. On peut aussi voir les expressions régulières comme une manière simple de décrire un automate fini.

Qu’est-ce qu’une expression régulière

En arithmétique, nous utilisons des symboles comme · et + pour construire une expression comme (2 + 3) · 4. En évaluant cette expression, nous obtenons un nombre. Une expression régulière est une suite de caractères et de quelques symboles spéciaux, par exemple a(x ∪ y), dont l’évaluation donne un langage (formel). Le résultat de l’expression (2 + 3) · 4 est le nombre 20, tandis que le résultat de l’expression régulière a(x ∪ y) est l’ensemble des deux mots « ax », « ay ».

Comment évaluerait-on l’expression régulière précédente a(x ∪ y) ? Chaque lettre est en fait une abréviation de l’ensemble à un seul élément contenant cette lettre, et la multiplication sous-entendue est la concaténation de mots. On pourrait réécrire l’expression régulière « en toutes lettres » ainsi :

{a}∘({x}∪{y})

On l’évaluerait ensuite de cette façon : la réunion {x} ∪ {y} nous donne le langage {x ; y}. En concaténant les langages {a} et {x ; y}, nous obtenons le langage {ax ; ay}.

Les expressions régulières sont très souvent utilisées en programmation, et la plupart des langages de programmation les implémentent d’une façon ou d’une autre. On s’en sert par exemple pour vérifier que le texte saisi par un utilisateur satisfait certains critères (par exemple, que c’est une adresse e-mail valide, une date valide, etc.), ou encore pour remplacer des textes (par exemple, on peut vouloir remplacer toutes les URL d’un texte par des liens cliquables, etc.).

Les implémentations réelles des expressions régulières sont généralement plus puissantes que les expressions régulières décrites ici, et utilisent une syntaxe légèrement différente, mais surtout plus compliquée.

Définition d’une expression régulière

Nous définirons une expression régulière sur un alphabet Σ. On dit alors qu’une expression régulière est :

  1. a, où a ∈ Σ. Autrement dit, une simple lettre de l’alphabet est une expression régulière.
  2. ϵ : le mot vide, qui s’écrit aussi en programmation par une chaîne vide "".
  3. ∅ : une expression régulière doit pouvoir décrire aussi le langage vide, donc le langage vide est une expression régulière.
  4. (R1 ∪ R2), où R1, R2 sont des expressions régulières.
  5. (R1 ∘ R2), où R1, R2 sont des expressions régulières.
  6. (R∗), où R est une expression régulière.

À la place du symbole ∪ du point 4, on peut aussi utiliser la barre verticale : |. À la place du symbole ∘, on peut n’utiliser rien du tout. De même que l’on n’écrit généralement pas le symbole de multiplication, le point ·, on n’écrit généralement pas non plus le symbole de concaténation ∘. Ces expressions régulières sont donc identiques : a ∘ (b ∪ c) et a(b|c).

Que signifient les différents opérateurs ?

  • ∪ ou | désigne la réunion de langages.
  • ∘ désigne la concaténation de langages.
  • ∗ désigne l’étoile d’un langage.

Exemples :

  • a désigne le langage simple {a}.
  • a|b désigne le langage constitué des deux mots {a ; b}.
  • a ∘ b désigne le langage {ab}.
  • a(b|c)d désigne le langage {abd ; acd}.
  • a(b∗) désigne le langage de tous les mots qui commencent par la lettre « a », suivie d’un nombre quelconque de lettres « b ».
  • (ab)∗ désigne le langage de tous les mots {ϵ ; ab ; abab ; ababab ; …}.
  • 0∗10∗ désigne le langage de tous les mots binaires qui contiennent exactement un 1. (Remarque que, pour être plus précis, on devrait écrire cette expression ainsi : (0∗)1(0∗), mais quand la notation reste lisible sans cela, on peut omettre les parenthèses.)
  • Σ∗1Σ∗ désigne le langage de tous les mots contenant au moins un 1.
  • (1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)∗ désigne le langage de tous les entiers naturels non nuls.

Nous allons ensuite montrer l’équivalence entre les expressions régulières et les automates finis. Pour toute expression régulière dont l’évaluation est un langage R, il existe un automate fini A tel que L(A) = R, et réciproquement.

Sources

Chapitres: Expressions régulières, Conversion d’une expression régulière en automate, Automate fini non déterministe généralisé, Conversion d’un automate en expression régulière