summaryrefslogtreecommitdiffstats
path: root/tp1.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2016-12-09 16:06:16 (GMT)
committerDavid A. Madore <david+git@madore.org>2016-12-09 16:06:16 (GMT)
commit4ea442db97dedd091906cf13f9897f3d29b2f6e4 (patch)
tree2bdaff39c8341a3a1c445e72ddbe350312f93a13 /tp1.tex
parent14fd5ab6468b545e59f90d18fbb704a668ef6a91 (diff)
downloadinf105-4ea442db97dedd091906cf13f9897f3d29b2f6e4.zip
inf105-4ea442db97dedd091906cf13f9897f3d29b2f6e4.tar.gz
inf105-4ea442db97dedd091906cf13f9897f3d29b2f6e4.tar.bz2
Explain how to produce a regexp that matches the multiples of 7 in base 10.
Diffstat (limited to 'tp1.tex')
-rw-r--r--tp1.tex39
1 files changed, 38 insertions, 1 deletions
diff --git a/tp1.tex b/tp1.tex
index b75720f..66dad72 100644
--- a/tp1.tex
+++ b/tp1.tex
@@ -1,6 +1,6 @@
%% This is a LaTeX document. Hey, Emacs, -*- latex -*- , get it?
\documentclass[12pt,a4paper]{article}
-\usepackage[a4paper,margin=2.5cm]{geometry}
+\usepackage[a4paper,margin=2cm]{geometry}
\usepackage[francais]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
@@ -333,6 +333,43 @@ son fonctionnement.
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}