Exercise on multiples of 7 in base 10.

1 files changed, 26 insertions, 0 deletions

diff --git a/tp1.tex b/tp1.tex
index e9ea79d..b75720f 100644
--- a/tp1.tex
+++ b/tp1.tex
@@ -309,6 +309,32 @@ rationnel au sens mathématique.
   contradiction (puisque $k+(i-1)n \neq k$).
 \end{corrige}
 
+%
+%
+%
+
+\exercice
+
+(a) Expliquer pourquoi il existe un automate déterministe fini sur le
+langage $\{0,1,2,\ldots,9\}$, ayant exactement $7$ états, qui accepte
+le langage formé des représentations décimales des entiers naturels
+multiples de $7$ (on ignorera les $0$ initiaux, i.e., on n'imposera
+pas que l'écriture décimale soit normalisée).
+
+(b) Utiliser un langage de programmation quelconque pour construire
+une expression rationnelle qui dénote le langage en question.  Tester
+son fonctionnement.
+
+\begin{corrige}
+(a) On construit l'automate dont l'ensemble des états est
+  $\{0,1,2,\ldots,6\}$ représentant les sept classes de congruence
+  possible d'un entier modulo $7$, la transition partant de $q \in
+  \{0,1,2,\ldots,6\}$ et étiquetée par $i \in \{0,1,2,\ldots,9\}$
+  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$.
+\end{corrige}
+
 
 %
 %