Les REGEX, pour
REGular EXpressions, sont un ensemble de commande permettant d'effectuer des recherches dans les chaines de caractères. Par exemple, nous avons demandé à un utilisateur d'entrer une adresse mail. Nous voulons nous assurer que la chaine de caractères saisi est au bon format
\[
\underbrace{\texttt{hebert.iut}}_{\text{(Des caractères)}}
\underbrace{\texttt{\at}}_{\text{(un arobase)}}
\underbrace{\texttt{gmail}}_{\text{(au moins 2 caractères)}}
\underbrace{\texttt{.}}_{\text{(un point)}}
\underbrace{\texttt{com}}_{\text{(entre 2 et 4 caractères)}}\]
Pour éviter de faire une recherche "à la main" à l'aide de boucle TANT QUE, on peut utiliser la REGEX suivante (en PHP par exemple)
1 :
preg_match("#^[a-zA-Z0-9]+@[a-zA-Z0-9]{2,}\.[a-z]{2,4}#",$chaine_saisi)
La fonction
preg_match retourne vrai si la REGEX passé en paramètre apparait dans la chaine du second paramètre. Il existe beaucoup d'autre fonction permettant de jouer avec les REGEX permettant de récupérer ou substituer des informations.
Mémento sur les REGEX.
Ce n'est pas l'objectif de ce cours mais gardons en tête quelques commande.
|
REGEX | Renvoie true si la chaine |
|
#Euler# | contient le mot Euler |
|
#Euler|euler# | contient le mot Euler ou euler |
|
#[Ee]uler# | contient le mot Euler ou euler |
|
#^Euler# | commence par Euler |
|
#Euler$# | finie par Euler |
|
#^Euler$# | ne contient que le mot Euler |
|
#[a-z]# | contient un lettre minuscule |
|
#[0-9]# | contient un chiffre |
|
#[1-3a-gF-H]# | contient un 1 ou 2 ou 3 ou une lettre minuscule parmi a, b, c, d, e, f, g ou une lettre majuscule parmi F, G, H |
|
#[^XYZ]# | ne contient pas X ou Y ou Z |
|
#[^A-Z]# | ne contient pas de lettre majuscule |
|
#^[^a-z]# | ne commence pas par une lettre minuscule |
|
#[^Euler]$# | ne finie pas E ou u ou l ou e ou r |
|
#Ha{2,4}# | contient le mot Haa ou Haa ou Haaa |
|
#(Ha){2,4}# | contient le mot HaHa ou HaHaHa ou HaHaHaHa |
|
#Ha+# | contient le mot qui commence par H suivit d'au moins un a. Cette REGEX équivaut à #Ha{1,}# |
|
#Ha?# | contient le mot H ou le mot Ha. Cette REGEX équivaut à #Ha{0,1}# |
|
#Ha*# | contient le mot H ou Ha ou Haa ou... . Cette REGEX équivaut à #Ha{0,}# |
|
#Goo*gle# | contient le mot Gogle ou Google ou Gooogle ... |
|
#ang?e# | contient le mot ange ou ane |
|
#Allo\?# | contient le mot Allo? |
Liens entre langage rationnel et REGEX
L'idée est de déterminer une REGEX qui permet de reconnaitre tous les mots d'un langage rationnel. Comme nous l'avons survoler précédement, une REGEX est un mot sur un alphabet augmenter de quelques opération. Comme on le voit dans le tableau précédent, en plus des caractère alphanumérique de notre alphabet, on utilise un ensemble de caractère spéciaux (le dollar, le crochet, la parenthèse etc).
Dans le cadre théorique dans lequel nous allons aborder ces REGEX, nous allons légèrement simplifier.
Définition
Soit \( \Sigma\) un alphabet. On définit l'alphabet augmenté \[\Sigma^+ = \Sigma \cup \{\varnothing, \varepsilon, (, ), +, *\}\]
Remarque
Pourquoi ces ajouts et pas d'autres ? L'idée est de trouver une correspondance parfaite entre les REGEX et les langages rationnels.
- \( \bullet\)
- L'ajout de \( \varnothing\) et \( \varepsilon\) va permettre d'avoir une REGEX qui correspond aux langages rationnels \( \varnothing\) et \( \{\varepsilon\}\) .
- \( \bullet\)
- L'ajout du \( +\) correspondra à l'union des langages
- \( \bullet\)
- L'ajout de \( *\) correspondra à l'étoile de Kleene
- \( \bullet\)
- Les parenthèses permettront de prioriser les opération (notamment entre la concaténation (équivalent d'une multiplication) et l'addition).
Définition
Soit \( \Sigma\) un alphabet. On note \( RE(\Sigma)\) l'ensemble des REGEX, mots sur \( \Sigma^+\) , construit de la manière suivante.
\begin{eqnarray*}
& &\varnothing\in RE(\Sigma)\\
& &\varepsilon\in RE(\Sigma)\\
\forall x\in \Sigma & & x\in RE(\Sigma)\\
\forall e_1, e_2\in RE(\Sigma) & & (e_1 + e_2) \in RE(\Sigma)\\
\forall e_1, e_2\in RE(\Sigma) & & (e_1e_2) \in RE(\Sigma)\\
\forall e\in RE(\Sigma) & & e^* \in RE(\Sigma)
\end{eqnarray*}
Remarque
Une autre manière de lire cette définition est :
- L'ensemble vide est une REGEX
- Le mot vide est une REGEX
- Toutes les lettres sont des REGEX
- La somme de REGEX est une REGEX
- La concaténation de REGEX est une REGEX
- L'étoile de Kleene d'une REGEX est une REGEX
Remarque
Attention, si \( e\) et \( f\) sont des REGEX alors \( e+f\) n'est pas une REGEX. En effet, la règle de l'addition dis que la REGEX est \( (e+f)\) (les parenthèses). Mais dans la pratique que nous allons en faire, la manipulation répétitive du parenthésage peut devenir très lourde.
Nous convenons donc de nous libérer de cette contrainte lorsqu'il n'y aura pas d'ambiguïté en considérant que la concaténation est prioritaire sur l'addition. Ainsi \( ef+g\) aura un sens, celui de \( ((ef)+g)\) et \( e(f+g)\) aura le sens de \( (e(f+g))\) .
Voici le résultat tant attendu.
Théorème
Soit \( \Sigma\) un alphabet. Il existe une unique application langage associé, noté \( L\) , satisfaisant les conditions suivantes :
\[
\begin{array}{lrcl}
&L : RE(\Sigma) & \longrightarrow & LR(\Sigma)\\
&\varnothing & \longmapsto & \varnothing\\
&\varepsilon & \longmapsto &\{\varepsilon\}\\
\forall x\in \Sigma, & x & \longmapsto &\{x\}\\
\forall e_1, e_2\in RE(\Sigma),& (e_1+e_2) & \longmapsto & L(e_1)\cup L(e_2)\\
\forall e_1, e_2\in RE(\Sigma), & (e_1e_2)& \longmapsto & L(e_1)L(e_2) \in RE(\Sigma)\\
\forall e\in RE(\Sigma), & e^* & \longmapsto & L(e)^* \in RE(\Sigma)
\end{array}
\]
De plus cette application est surjective.
Démonstration
Admise.
Remarque
Une autre manière de lire les règles de la fonction langage associé est :
- \( L\left(\varnothing\right)=\varnothing\)
- \( L\left(\varepsilon\right)=\{\varepsilon\}\)
- \( \forall x \in \Sigma\) , \( L\left(x\right)=\{x\}\)
- \( \forall e_1, e_2\in RE(\Sigma)\) , \( L\left(e_1\right)\cup L\left(e_2\right)=L(e_1+e_2)\)
- \( \forall e_1, e_2\in RE(\Sigma)\) , \( L\left(e_1\right)L\left(e_2\right)=L\left(e_1e_2\right)\)
- \( \forall e\in RE(\Sigma)\) , \( L\left(e\right)^*=L\left(e^*\right)\)
Remarque
La surjectivité de l'application langage associé se reformule en disant qu'il existe (au moins) une REGEX à tout langage rationnel.
Exemple
Sur l'alphabet \( \Sigma=\{a, b, c\}\) quel est le langage rationnel associé à la REGEX \( ab+c\) ?
La question reviens à calculer \( L(ab+c)\) , en utilisant les règles de la fonction \( L\) on a
\begin{eqnarray*}
L(ab+c) &=& L(ab)\cup L(c)\\
&=& L(a)L(b)\cup L(c)\\
&=& \{a\}\{b\}\cup \{c\}\\
&=& \{ab\}\cup \{c\}\\
&=& \{ab, c\}\\
\end{eqnarray*}
Exercice
On fixe l'alphabet \( \Sigma=\{a, b, c\}\) . Pour chacune des REGEX suivantes déterminer le langage rationnel.
- \( \varepsilon\)
- \( a\)
- \( a+b\)
- \( ab+c\)
- \( a(b+c)\)
- \( a^*\)
- \( (ab)^*\)
- \( (a+b)^*\)
Exercice
On fixe l'alphabet \( \Sigma=\{a, b, c\}\) . Déterminer, si possible, une REGEX associée aux langages suivantes.
- \( L=\{\varepsilon\}\)
- \( L=\{a, b, c\}\)
- \( L=\{a, ab, ac\}\)
- \( L=\{a^n | n\in \N\}\)
- \( L=\{a^{2n} | n\in \N\}\)
- \( L=\{b, ab, aab, aaab, aaaab, \ldots\}\)
- \( L=\{c, b, ab, aab, aaab, aaaab, \ldots\}\)
1
Le langage de REGEX utilisé ici est le
BRE (Basic Regular Expression), il en existe d'autre comme par exemple le
ERE (Extended Regular Expression), le
PCRE (Perl Compatible Regular Expressions) fort de sa comptatibilité avec le langage java.
