From 4ea442db97dedd091906cf13f9897f3d29b2f6e4 Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
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')

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.2.3