A simple exercise on using egrep.

2 files changed, 212 insertions, 0 deletions

diff --git a/tp1-files/liste1 b/tp1-files/liste1
new file mode 100644
index 0000000..ca3cf28
--- /dev/null
+++ b/tp1-files/liste1
@@ -0,0 +1,24 @@
+
+a
+aa
+aaa
+aaaaaaa
+aaabbb
+aab
+aabaa
+aabaaaaabb
+ab
+aba
+ababb
+ababba
+abb
+abbbb
+b
+ba
+baa
+bab
+bb
+bba
+bbabbb
+bbb
+bbbbbb
diff --git a/tp1.tex b/tp1.tex
new file mode 100644
index 0000000..fd19232
--- /dev/null
+++ b/tp1.tex
@@ -0,0 +1,188 @@
+%% This is a LaTeX document.  Hey, Emacs, -*- latex -*- , get it?
+\documentclass[12pt,a4paper]{article}
+\usepackage[a4paper,margin=2.5cm]{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
+
+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}
+
+
+%
+%
+%
+\end{document}