summaryrefslogtreecommitdiffstats
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
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.
-rwxr-xr-xtp1-files/multiples7.pl40
-rw-r--r--tp1.tex39
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}