path: root/tp1.tex

%% This is a LaTeX document.  Hey, Emacs, -*- latex -*- , get it?
\documentclass[12pt,a4paper]{article}
\usepackage[a4paper,margin=2cm]{geometry}
\usepackage[francais]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
%\usepackage{ucs}
\usepackage{times}
% A tribute to the worthy AMS:
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
%
\usepackage{mathrsfs}
\usepackage{wasysym}
\usepackage{url}
%
\usepackage{graphics}
\usepackage[usenames,dvipsnames]{xcolor}
\usepackage{tikz}
\usetikzlibrary{arrows,automata,positioning}
\usepackage[hyperindex=false]{hyperref}
%
\theoremstyle{definition}
\newtheorem{comcnt}{Tout}
\newcommand\thingy{%
\refstepcounter{comcnt}\smallbreak\noindent\textbf{\thecomcnt.} }
\newcommand\exercice{%
\refstepcounter{comcnt}\bigbreak\noindent\textbf{Exercice~\thecomcnt.}}
\renewcommand{\qedsymbol}{\smiley}
%
\newcommand{\liff}{\mathrel{\Longleftrightarrow}\relax}
%
\DeclareUnicodeCharacter{00A0}{~}
\DeclareUnicodeCharacter{03B5}{$\varepsilon$}
%
\DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C}
\DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D}
%
%
\DeclareFontFamily{U}{manual}{} 
\DeclareFontShape{U}{manual}{m}{n}{ <->  manfnt }{}
\newcommand{\manfntsymbol}[1]{%
    {\fontencoding{U}\fontfamily{manual}\selectfont\symbol{#1}}}
\newcommand{\dbend}{\manfntsymbol{127}}% Z-shaped
\newcommand{\danger}{\noindent\hangindent\parindent\hangafter=-2%
  \hbox to0pt{\hskip-\hangindent\dbend\hfill}}
%
\newcommand{\spaceout}{\hskip1emplus2emminus.5em}
\newif\ifcorrige
\corrigetrue
\newenvironment{corrige}%
{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi%
\smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}}
{{\hbox{}\nobreak\hfill\checkmark}%
\ifcorrige\relax\else\egroup\fi\par}
%
%
% NOTE: compile dot files with
% dot2tex --figonly -f tikz --tikzedgelabels --graphstyle=automaton file.dot  > file.tex
\tikzstyle{automaton}=[>=stealth',initial text={},thick,every loop/.style={min distance=7mm,looseness=5}]
\tikzstyle{state}=[]
\tikzstyle{final}=[accepting by arrow]
%
%
%
\begin{document}
\ifcorrige
\title{TP \texttt{egrep} — Corrigé}
\else
\title{TP \texttt{egrep}}
\fi
\author{David A. Madore}
\maketitle

\centerline{\textbf{INF105}}

{\footnotesize
\immediate\write18{sh ./vc > vcline.tex}
\begin{center}
Git: \input{vcline.tex}
\end{center}
\immediate\write18{echo ' (stale)' >> vcline.tex}
\par}

\pretolerance=8000
\tolerance=50000


%
%
%

Le programme Unix \texttt{egrep} a pour fonction de rechercher
(\emph{filtrer}) les lignes d'un fichier dont une partie (au sens :
facteur d'un mot) vérifie une certaine expression rationnelle.  La
syntaxe est : « \texttt{egrep} \textit{regexp} \textit{fichiers} » où
\textit{regexp} désigne l'expression à chercher et \textit{fichiers}
la liste des fichiers (un par argument) dans lesquels la recherche
doit être menée : par exemple, « \texttt{egrep toto monfichier} »
cherche dans \texttt{monfichier} toutes les lignes contenant
\texttt{toto} ; en retour, \texttt{egrep} produit les lignes
recherchées, éventuellement précédées du nom du fichier où elles ont
été trouvées, et en colorisant éventuellement la partie qui vérifie
l'expression (selon les options passées et/ou la configuration).

\texttt{egrep} comporte de nombreuses options et particularités
d'expressions rationnelles, dont la liste peut être connue en
consultant le manuel (« \texttt{man egrep} »).  Par exemple, l'option
\texttt{-c} sert à compter le nombre de lignes trouvées au lieu de les
afficher.

Il faut prendre garde au fait que le shell Unix va interpréter
certains caractères spéciaux : le moyen le plus simple de l'éviter est
d'entourer le paramètre à protéger de caractères \texttt{\char"27}
(apostrophe droite, ou guillemet simple), qui protège tous les
caractères jusqu'au prochain caractère \texttt{\char"27} rencontré.
Par exemple, « \texttt{egrep \char"27xy*z\char"27{} monfichier} »
cherche dans \texttt{monfichier} toutes les lignes dont une partie
vérifie l'expression rationnelle \texttt{xy*z}, c'est-à-dire, les
lignes contenant un \texttt{x} suivi d'un nombre quelconque
(éventuellement nul) de \texttt{y} et d'un \texttt{z}.

Pour rechercher les lignes vérifiant une certaine expression
rationnelle du début à la fin, on peut utiliser les caractères
spéciaux \texttt{\char"5E} et \texttt{\char"24} qui servent à ancrer
l'expression au début et à la fin de la chaîne respectivement : par
exemple, « \texttt{egrep \char"27\char"5Ex\char"27{} monfichier} »
renvoie les lignes de \texttt{monfichier} qui commencent par
\texttt{x}, et « \texttt{egrep \char"27\char"5Exy*z\char"24\char"27{}
    monfichier} » renvoie celles qui sont exactement formées d'un
\texttt{x} (en début de ligne) suivi d'un nombre quelconque de
\texttt{y} et d'un \texttt{z} (en fin de ligne).

%
%
%

\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 24 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,
par exemple en tapant \texttt{cat \char"7Emadore/inf105/liste1} pour
l'afficher dans le terminal.)  Utiliser \texttt{egrep} pour répondre
aux questions suivantes :

(a) Combien de mots de cette liste ne contiennent aucun \texttt{a} ?

(b) Combien de mots commencent par \texttt{b} ?

(c) Combien de mots sont formés d'un nombre quelconque de \texttt{a}
suivi d'un nombre quelconque de \texttt{b} ?

(d) Combien de mots sont formés d'un nombre non nul de \texttt{a}
suivi d'un nombre non nul de \texttt{b} ?

(e) Dans combien de mots chaque \texttt{a} est-il suivi d'(au moins)
un \texttt{b} ?

(f) Dans combien de mots le nombre de \texttt{a} est-il congru à $1$
modulo $3$ ?

\begin{corrige}
(a) \verb=egrep -c '^b*$'= (ou bien \verb='^[^a]*$'=)
  renvoie $5$.

(b) \verb=egrep -c '^b'= (ou bien \verb='^b(a|b)*$'= ou encore
  \verb='^b[ab]*$'=) renvoie $9$.

(c) \verb=egrep -c '^a*b*$'= renvoie $14$.

(d) \verb=egrep -c '^aa*bb*$'= (ou bien \verb='^a+b+$'=) renvoie $5$.

(e) \verb=egrep -c '^b*(abb*)*$'= (ou bien \verb='^b*(ab+)*$'=) ou
  \verb='^(b|ab)*$'= renvoie $11$.

(f) Si l'alphabet ne contenait que la lettre \texttt{a}, l'expression
  rationnelle désignant le langage constitué des mots formé d'un
  nombre de $a$ congru à $1$ modulo $3$ s'écrirait \texttt{a(aaa)*}.
  On intercale des \texttt{b*} dans cette expression de manière à les
  ignorer : \verb=egrep -c '^b*a(b*ab*ab*a)*b*$'= (ou bien
  \verb='^b*ab*(ab*ab*ab*)*$'= ou toutes sortes d'autres variantes)
  renvoie $11$.
\end{corrige}

%
%
%

\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}.

(a) Combien de lignes ne contiennent que des lettres de l'alphabet
latin (de A à Z sans diacritiques, majuscules comme minuscules) ?  (On
rappelle pour cela la syntaxe « \texttt{[abc]} » d'\texttt{egrep} qui
permet de désigner un caractère parmi \texttt{a}, \texttt{b} et
\texttt{c} (c'est donc synonyme de \texttt{(a|b|c)} mais uniquement
pour des caractères individuels) et « \texttt{[a-f]} » qui désigne un
caractère entre \texttt{a} et \texttt{f}.)  Combien de lignes
contiennent un caractère autre que les lettres de l'alphabet latin ?
(On rappelle que « \texttt{[\char"5Ea-f]} » permet de désigner un
caractère n'appartenant pas à l'intervalle entre \texttt{a} et
\texttt{f}.)

(b) Combien de lignes commencent par un \texttt{a} et finissent par un
\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 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 ?

(d) Combien de lignes contiennent exactement six caractères ?  (On
rappelle les syntaxes « \texttt{$r$\{$n$\}} » et
« \texttt{$r$\{$m$,$n$\}} » et « \texttt{$r$\{$m$,\}} » et
« \texttt{$r$\{,$n$\}} » pour chercher respectivement exactement $n$,
entre $m$ et $n$, au moins $m$, et au plus $n$ occurrences
consécutives\footnote{I.e., \texttt{$r$\{4\}} équivaut à $rrrr$ et
  \texttt{$r$\{1,3\}} équivaut à $(r|rr|rrr)$ par exemple.} de
l'expression régulière $r$.)  Entre quatre et huit caractères ?  Au
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
  (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}

%
%
%

\exercice

{\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 parenthè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.

\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}

%
%
%

\exercice

(a) Expliquer pourquoi il existe un automate déterministe fini sur le
langage $\{0,1,2,\ldots,9\}$, ayant exactement $7$ états, qui accepte
le langage formé des représentations décimales des entiers naturels
multiples de $7$ (on ignorera les $0$ initiaux, i.e., on n'imposera
pas que l'écriture décimale soit normalisée).

(b) Utiliser un langage de programmation quelconque pour construire
une expression rationnelle qui dénote le langage en question.  Tester
son fonctionnement.

\begin{corrige}
(a) On construit l'automate dont l'ensemble des états est
  $\{0,1,2,\ldots,6\}$ représentant les sept classes de congruence
  possible d'un entier modulo $7$, la transition partant de $q \in
  \{0,1,2,\ldots,6\}$ et étiquetée par $i \in \{0,1,2,\ldots,9\}$
  aboutissant à $10q+i$ modulo $7$ (c'est-à-dire à l'état étiqueté par
  l'unique élément de $\{0,1,2,\ldots,6\}$ qui est congru à $10q+i$
  modulo $7$), ou, si on préfère, $3q+i$.

(b) L'algorithme sera essentiellement le suivant : on initialise un
  tableau $T$ à double entrées $q_1$ et $q_2$ (chacun variant de $0$
  à $6$ inclus) de chaînes de caractères en plaçant dans la case
  $[q_1][q_2]$ soit le seul $i \in \{0,\ldots,9\}$ tel que $q_2 \equiv
  3q_1+1$ (vu comme une chaîne de caractères de longueur $1$) soit la
  concaténation des tels $i$ entourés par des crochets (pour utiliser
  la syntaxe d'\texttt{egrep} selon laquelle \texttt{[07]} désigne
  l'un des deux caractères \texttt{0} ou \texttt{7}).  Ensuite, on
  effectue une boucle triple : pour $q_e$ (l'état à éliminer)
  parcourant tous les états sauf un dans un certain ordre, disons en
  décroissant de $6$ à $1$, et $q_1$ et $q_2$ parcourant chacun
  indépendamment tous les états non encore éliminés (donc tous les
  états de $0$ à $q_e-1$ si on élimine en décroissant de $6$ à $1$),
  on remplace $T[q_1][q_2]$ par la chaîne
\[
``\texttt{(}" + T[q_1][q_2] + ``\texttt{|}" + T[q_1][q_e] + T[q_e][q_e] + ``\texttt{*}" + T[q_e][q_2] + ``\texttt{)}"
\]
  où $+$ désigne la concaténation des chaînes de caractères et $``x"$
  désigne la chaîne contenant le seul caractère $x$.  Au final, on
  retourne $``\texttt{\char"5E}" + T[q_0][q_0] +
  ``\texttt{*\char"24}"$ (où $q_0$ est le seul état non éliminé).

Si on élimine les états en décroissant de $6$ à $1$, on obtient une
chaîne de longueur $16\thinspace 915$ qui commence par
\begin{center}
\verb=^(((((([07]|6[29]*3)|(5|6[29]*[18])(4|5[29]*[18])*(6|5[29]*3))=
\end{center}
et qui finit par
\begin{center}
\verb=][29]*3)|([07]|[18][29]*[18])(4|5[29]*[18])*(6|5[29]*3))))))*$=
\end{center}
On peut par exemple tester son fonctionnement en vérifiant que
\texttt{seq 0 10000 | egrep "\char"24(calcule\char"5F{}regexp)"} (où
\texttt{calcule\char"5F{}regexp} est le programme qui la calcule) et
\texttt{seq 0 7 10000} produisent des sorties identiques (le programme
Unix \texttt{seq} sert à produire une liste d'entiers).
\end{corrige}

%
%
%

\exercice

Sachant que \texttt{/usr/share/dict/american-english} contient un
dictionnaire de mots anglais, trouver trois mots anglais qui
commencent par les lettres « he » et finissent par les lettres « he »
(i.e., qui ont « he » comme préfixe et « he » comme suffixe).

\begin{corrige}
On peut utiliser la commande
\begin{center}
\verb=egrep -i '^he.*he$' /usr/share/dict/american-english=
\end{center}
qui renvoie les deux mots « headache » et « heartache », Mais il y a
un piège, c'est que cette expression rationnelle omet une solution, à
savoir le mot « he » lui-même.
\end{corrige}


%
%
%
\end{document}