summaryrefslogtreecommitdiffstats
path: root/tp1-files
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2016-12-09 16:06:16 (GMT)
committerDavid A. Madore <david+git@madore.org>2016-12-09 16:06:16 (GMT)
commit4ea442db97dedd091906cf13f9897f3d29b2f6e4 (patch)
tree2bdaff39c8341a3a1c445e72ddbe350312f93a13 /tp1-files
parent14fd5ab6468b545e59f90d18fbb704a668ef6a91 (diff)
downloadinf105-4ea442db97dedd091906cf13f9897f3d29b2f6e4.zip
inf105-4ea442db97dedd091906cf13f9897f3d29b2f6e4.tar.gz
inf105-4ea442db97dedd091906cf13f9897f3d29b2f6e4.tar.bz2
Explain how to produce a regexp that matches the multiples of 7 in base 10.
Diffstat (limited to 'tp1-files')
-rwxr-xr-xtp1-files/multiples7.pl40
1 files changed, 40 insertions, 0 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";