Explain how to produce a regexp that matches the multiples of 7 in base 10.

2 files changed, 78 insertions, 1 deletions

diff --git a/tp1-files/multiples7.pl b/tp1-files/multiples7.pl
new file mode 100755
index 0000000..67e5a06
--- /dev/null
+++ b/tp1-files/multiples7.pl
@@ -0,0 +1,40 @@
+#! /usr/local/bin/perl -w
+
+use strict;
+use warnings;
+
+# Tableau des transitions q1→q2
+my @transitions;
+
+# Création de l'automate initial
+for ( my $q1=0 ; $q1<7 ; $q1++ ) {
+    for ( my $i=0 ; $i<10 ; $i++ ) {
+	my $q2 = (3*$q1+$i)%7;
+	push @{$transitions[$q1][$q2]}, $i;
+    }
+}
+
+# Transformation des transitions en regexps
+for ( my $q1=0 ; $q1<7 ; $q1++ ) {
+    for ( my $q2=0 ; $q2<7 ; $q2++ ) {
+	my $s = join("",@{$transitions[$q1][$q2]});
+	$s = "[$s]" if length($s)>1;
+	$transitions[$q1][$q2] = $s;
+    }
+}
+
+# Élimination des états
+for ( my $qelim=6 ; $qelim>=0 ; $qelim-- ) {
+    for ( my $q1=0 ; $q1<$qelim ; $q1++ ) {
+	for ( my $q2=0 ; $q2<$qelim ; $q2++ ) {
+	    my $r12 = $transitions[$q1][$q2];
+	    my $r1 = $transitions[$q1][$qelim];
+	    my $s = $transitions[$qelim][$qelim];
+	    my $r2 = $transitions[$qelim][$q2];
+	    $transitions[$q1][$q2] = "(${r12}|${r1}${s}\*${r2})";
+	}
+    }
+}
+
+# Impression de la regexp finale
+print "\^" . $transitions[0][0] . "\*\$\n";
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}