diff options
Diffstat (limited to 'tp1.tex')
| -rw-r--r-- | tp1.tex | 39 |
1 files changed, 38 insertions, 1 deletions
@@ -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} |