summaryrefslogtreecommitdiffstats
path: root/tp1.tex
blob: 3baac07da032333fa103f736b8a54dad08a12863 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
%% 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 colorisation).

\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 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,
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+)*$'=)
  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 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 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.

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


%
%
%
\end{document}