diff options
| -rwxr-xr-x | tp1-files/multiples7.pl | 40 | ||||
| -rw-r--r-- | tp1.tex | 39 |
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"; @@ -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} |