From 4ea442db97dedd091906cf13f9897f3d29b2f6e4 Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Fri, 9 Dec 2016 17:06:16 +0100
Subject: Explain how to produce a regexp that matches the multiples of 7 in
 base 10.

---
 tp1.tex | 39 ++++++++++++++++++++++++++++++++++++++-
 1 file changed, 38 insertions(+), 1 deletion(-)

(limited to 'tp1.tex')

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}
 
 
-- 
cgit v1.2.3