Exercise on backreferences.

2 files changed, 82 insertions, 11 deletions

diff --git a/tp1-files/liste2 b/tp1-files/liste2
index c47b811..f77f2a4 100644
--- a/tp1-files/liste2
+++ b/tp1-files/liste2
@@ -2,8 +2,11 @@
 * *
 * * *
 alcatraz
+allez
+allume-gaz
 aujourd'hui
 *coucou*
 regexp
+tonton
 toto
 turlututu chapeau pointu
diff --git a/tp1.tex b/tp1.tex
index 8a22749..e9ea79d 100644
--- a/tp1.tex
+++ b/tp1.tex
@@ -139,6 +139,9 @@ renvoie les lignes de \texttt{monfichier} qui commencent par
 
 \exercice
 
+{\footnotesize (Le but de cet exercice est d'utiliser \texttt{egrep}
+  dans un cadre proche du cadre théorique vu en cours.)\par}
+
 Le fichier \texttt{\char"7Emadore/inf105/liste1} contient 25 mots sur
 l'alphabet $\{\texttt{a},\texttt{b}\}$, tous distincts, à raison de un
 par ligne.  (On pourra commencer par jeter un coup d'œil au fichier,
@@ -191,6 +194,11 @@ modulo $3$ ?
 
 \exercice
 
+{\footnotesize (Le but de cet exercice est d'introduire quelques
+  fonctionalités de \texttt{egrep} qui ne dépassent pas le cadre
+  théorique des expressions rationnelles mais qui sont néanmoins
+  utiles en pratique.)\par}
+
 Le fichier \texttt{\char"7Emadore/inf105/liste2} contient des mots
 (tous distincts) sur l'alphabet ASCII ; ces lignes peuvent contenir,
 notamment, des espaces et des caractères spéciaux pour \texttt{egrep}.
@@ -211,7 +219,7 @@ caractère n'appartenant pas à l'intervalle entre \texttt{a} et
 \texttt{z} ?  (On rappelle pour cela la syntaxe « \texttt{.} »
 d'\texttt{egrep} qui permet de désigner un caractère quelconque.)
 
-(c) Combien de lignes contiennent une astérisque ?  (On rappelle qu'on
+(c) Combien de lignes contiennent un astérisque ?  (On rappelle qu'on
 peut « échapper » un caractère spécial pour \texttt{egrep} en le
 faisant précéder d'un backslash (\texttt{\char"5C}).)  Au moins deux
 astérisques ?  Exactement deux astérisques ?
@@ -226,19 +234,79 @@ moins trois fois le caractère \texttt{u} ?  Exactement six fois le
 caractère \texttt{u} ?
 
 \begin{corrige}
-(a) \verb=egrep -c '^[A-Za-z]*$'= pour uniquement des lettres, et
-  \verb='[^A-Za-z]'= pour un caractère qui n'est pas une lettre.
+(a) \verb=egrep -c '^[A-Za-z]*$'= pour uniquement des lettres
+  (renvoie $5$), et \verb='[^A-Za-z]'= pour un caractère qui n'est pas
+  une lettre (renvoie $7$).
+
+(b) \verb=egrep -c '^a.*z$'= (renvoie $3$)
+
+(c) \verb=egrep -c '\*'= pour un astérisque (renvoie $4$),
+  \verb='\*.*\*'= pour au moins deux (renvoie $3$), et enfin
+  \verb='^[^*]*\*[^*]*\*[^*]*$'= pour exactement deux astérisques
+  (renvoie $2$).
+
+(d) \verb=egrep -c '^.{6}$'= pour exactement six caractères
+  (renvoie $2$), \verb='^.{4,8}$'= pour entre quatre et huit
+  caractères (renvoie $7$), \verb='(u.*){3,}'= pour au moins trois
+  fois \texttt{u} (renvoie $2$), et \verb='^[^u]*(u[^u]*){6}$'= pour
+  exactement six \texttt{u} (renvoie $1$).
+\end{corrige}
 
-(b) \verb=egrep -c '^a.*z$=
+%
+%
+%
+
+\exercice
 
-(c) \verb=egrep -c '\*'= pour une astérisque, \verb='\*.*\*'= pour au
-  moins deux, et \verb='[^*]*\*[^*]*\*[^*]*'= pour exactement deux
-  astérisques.
+{\footnotesize (Le but de cet exercice est d'évoquer une fonctionalité
+  de \texttt{egrep} souvent importante dans la pratique et qui dépasse
+  le cadre des expressions rationnelles au sens mathématique : les
+  \emph{références arrière}.)\par}
+
+La syntaxe \texttt{\char"5C$n$} d'\texttt{egrep}, où $n$ est un
+chiffre entre $1$ et $9$, constitue une \emph{référence arrière} (ou
+\emph{backreference} en anglais) : cette extension au mécanisme
+général des expressions rationnelles permet de demander une répétition
+du même facteur qui a été « capturé » par un bloc de parenthèses
+antérieur (les blocs de parenthèses étant numérotés dans l'ordre de
+leurs parenthèses ouvrantes : ainsi \texttt{\char"5C{}1} désigne la
+chaîne de caractères qui a été vérifié par le bloc de parenthèses
+s'ouvrant à la première parentèse ouvrante).  Par exemple,
+\texttt{(foo|bar)x*\char"5C{}1} recherche une occurrence de
+\texttt{foo} ou bien \texttt{bar}, suivi d'un nombre quelconque de
+\texttt{x}, suivi de la \emph{même} chaîne \texttt{foo} ou
+\texttt{bar} que précédemment (c'est donc équivalent à
+\texttt{(foox*foo|barx*bar)} mais pas à
+\texttt{(foo|bar)x*(foo|bar)}).
+
+(a) Comment utiliser \texttt{egrep} pour rechercher les lignes de
+\texttt{liste1} qui sont formées d'un certain nombre de \texttt{a},
+puis de \texttt{b}, puis du \emph{même} nombre de \texttt{a} que
+précédemment ?
+
+(b) Montrer qu'on ne pourrait pas faire cette recherche sans la
+fonctionalité additionnelle des références arrière, au sens où la
+recherche faite dans la question précédente ne définit pas un langage
+rationnel au sens mathématique.
 
-(d) \verb=egrep -c '^.{6}$'= pour exactement six caractères,
-  \verb='^.{4,8}$'= pour entre quatre et huit caractères,
-  \verb='(u.*){3,}'= pour au moins trois fois \texttt{u}, et
-  \verb='^[^u]*(u[^u]*){6}$'= pour exactement six \texttt{u}.
+\begin{corrige}
+(a) On utilise \verb=egrep '^(a*)b\1$'= (qui renvoie trois lignes).
+
+(b) Il s'agit de montrer que le langage $L := \{a^n b a^n :
+  n\in\mathbb{N}\}$ constitué des mots formées d'un certain nombre de
+  $a$, suivis de $b$ puis du même nombre de $a$, n'est pas rationnel.
+  On utilise pour cela le lemme de pompage : supposons par l'absurde
+  que $L$ soit rationnel, et soit $k$ tel que donné par le lemme de
+  pompage ; considérons alors le mot $t := a^k b a^k \in L$ : il
+  devrait admettre une factorisation $t = uvw$ vérifiant (i) $|v|\geq
+  1$, (ii) $|uv|\leq k$ et (iii) $uv^iw \in L$ pour tout $i\in
+  \mathbb{N}$.  La propriété (ii), vu que $t$ commence par $a^k$,
+  garantit que $u$ et $v$ sont formés entièrement de la lettre $a$,
+  disons $u = a^m$ et $v = a^n$ (où $m = |u|$ et $n = |v|$), en notant
+  que $n \geq 1$ d'après (i) ; on a alors $w = a^{k-m-n} b a^k$, et
+  $uv^iw = a^{m + in + (k-m-n)} v a^k = a^{k+(i-1)n} b a^k$ est censé
+  appartenir à $L$ pour tout $i$ ; en prenant $i \neq 1$, on a une
+  contradiction (puisque $k+(i-1)n \neq k$).
 \end{corrige}