From 4ea442db97dedd091906cf13f9897f3d29b2f6e4 Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Fri, 9 Dec 2016 17:06:16 +0100 Subject: Explain how to produce a regexp that matches the multiples of 7 in base 10. --- tp1-files/multiples7.pl | 40 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 40 insertions(+) create mode 100755 tp1-files/multiples7.pl (limited to 'tp1-files/multiples7.pl') 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"; -- cgit v1.1