diff options
| -rw-r--r-- | tp1.tex | 26 |
1 files changed, 26 insertions, 0 deletions
@@ -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} + % % |