summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2016-12-09 15:54:11 +0100
committerDavid A. Madore <david+git@madore.org>2016-12-09 15:54:11 +0100
commit14fd5ab6468b545e59f90d18fbb704a668ef6a91 (patch)
treedf934690c928641d213996d9f9640729c9cdcec9
parentf56f57e1462ea3e065943b94ae3c2eb352296099 (diff)
downloadinf105-14fd5ab6468b545e59f90d18fbb704a668ef6a91.tar.gz
inf105-14fd5ab6468b545e59f90d18fbb704a668ef6a91.tar.bz2
inf105-14fd5ab6468b545e59f90d18fbb704a668ef6a91.zip
Exercise on multiples of 7 in base 10.
-rw-r--r--tp1.tex26
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}
+
%
%