JFiZO - Zadanie 09.013

Automat:

Automat można „zwinąć” w ten sposób:

Na pierwszym grafie usunąłem ścieżki prowadzące do „martwych” stanów. Na drugim „zwinąłem” rogi – usunąłem je (te wierzchołki) jednocześnie wstawiając do grafu krawędzie, które zachowują równoważność z grafem z rogami. Na trzecim grafie zrobiłem osobny stan początkowy i osobny stan końcowy. Na czwartym usunąłem kolejny wierzchołek. Po czym stwierdziłem, że tyle kroków wystarczy by zobaczyć sens algorytmu, a efekt końcowy będzie równie nieczytelny co skrypt perlowy dude'a, więc pozostawię usunięcie reszty zbędnych wierzchołków czytelnikowi (ew. komuś przy tablicy).

\left(a(dc+cd)^*b+b(dc+cd)^*a+c(ab+ba)^*d+d(ab+ba)^*c + adbc + bdac + acbd + bcad + cadb + dacb + cbda + dbca\right)^*

Nie przechodzi adbacb

Wygenerowane programem w perlu, lol http://dude.bshellz.net/zad13.pl

• regexp: (cd + ba + dc + ab + (bd + db)(cd + ab)*(ca + ac) + (cb + bc + (bd + db)(cd + ab)*cc)(ab + dc + dd(cd + ab)*cc)*(ad + da + dd(cd + ab)*(ca + ac)) + (da + ad + (bd + db)(cd + ab)*aa + (cb + bc + (bd + db)(cd + ab)*cc)(ab + dc + dd(cd + ab)*cc)*(dd(cd + ab)*aa))(ba + cd + bb(cd + ab)*aa + (bb(cd + ab)*cc)(ab + dc + dd(cd + ab)*cc)*(dd(cd + ab)*aa))*(bc + cb + bb(cd + ab)*(ca + ac) + (bb(cd + ab)*cc)(ab + dc + dd(cd + ab)*cc)*(ad + da + dd(cd + ab)*(ca + ac))) + (ca + ac + (cb + bc + (bd + db)(cd + ab)*cc)(ab + dc + dd(cd + ab)*cc)*aa + (da + ad + (bd + db)(cd + ab)*aa + (cb + bc + (bd + db)(cd + ab)*cc)(ab + dc + dd(cd + ab)*cc)*(dd(cd + ab)*aa))(ba + cd + bb(cd + ab)*aa + (bb(cd + ab)*cc)(ab + dc + dd(cd + ab)*cc)*(dd(cd + ab)*aa))*(cc + (bb(cd + ab)*cc)(ab + dc + dd(cd + ab)*cc)*aa))(ba + dc + bb(ab + dc + dd(cd + ab)*cc)*aa + (dd + bb(ab + dc + dd(cd + ab)*cc)*(dd(cd + ab)*aa))(ba + cd + bb(cd + ab)*aa + (bb(cd + ab)*cc)(ab + dc + dd(cd + ab)*cc)*(dd(cd + ab)*aa))*(cc + (bb(cd + ab)*cc)(ab + dc + dd(cd + ab)*cc)*aa))*(bd + db + bb(ab + dc + dd(cd + ab)*cc)*(ad + da + dd(cd + ab)*(ca + ac)) + (dd + bb(ab + dc + dd(cd + ab)*cc)*(dd(cd + ab)*aa))(ba + cd + bb(cd + ab)*aa + (bb(cd + ab)*cc)(ab + dc + dd(cd + ab)*cc)*(dd(cd + ab)*aa))*(bc + cb + bb(cd + ab)*(ca + ac) + (bb(cd + ab)*cc)(ab + dc + dd(cd + ab)*cc)*(ad + da + dd(cd + ab)*(ca + ac)))))*
• kod:

#!/usr/bin/perl -w
use strict;

my $start;
my $finish;
my %trans;

while (<>) {
        chomp;
        next if !$_;
        if (/^S:\s*(\(.*\))/) {
                $start = $1;
        } elsif (/^F:\s*(\(.*\))/) {
                $finish = $1;
        } elsif (/(\(.*?\))\s*-(.*?)>\s*(\(.*?\))/) {
                if ($trans{$1}->{$3}) {
                        $trans{$1}->{$3} .= " + $2";
                } else {
                        $trans{$1}->{$3} = "$2";
                }
        }
}

while (keys %trans > 1) {
        for my $toremove (keys %{$trans{$start}}) {
                next if $toremove eq $start;
                my $loop = "";
                if ($trans{$toremove}->{$toremove}) {
                        $loop = "($trans{$toremove}->{$toremove})*";
                }
                        
                for my $neigh (keys %trans) {
                        next if $neigh eq $toremove;
                        next unless ($trans{$neigh}->{$toremove});
                        my $via = $trans{$neigh}->{$toremove};
                        $via = "($via)" if ($via =~ /(\+\s)/);

                        for my $dist (keys %{$trans{$toremove}}) {
                                next if $dist eq $toremove;
                                my $via2 = $trans{$toremove}->{$dist};
                                $via2 = "($via2)" if ($via2 =~ /(\+\s)/);
                                my $path = "$via$loop$via2";
                                if ($trans{$neigh}->{$dist}) {
                                        $trans{$neigh}->{$dist} .= " + $path";
                                } else {
                                        $trans{$neigh}->{$dist} = "$path";
                                }
                        }
                        delete $trans{$neigh}->{$toremove};
                }
                delete $trans{$toremove};
        }
}

my $loop = "";
if ($trans{$start}->{$start}) {
        $loop = "($trans{$start}->{$start})*";
}
my $path = "";
if ($trans{$start}->{$finish}) {
        $path = $trans{$start}->{$finish};
}
$path = "$loop$path";
$path =~ s/e([a-df-z]+)/$1/g;
$path =~ s/([a-df-z]+)e/$1/g;
print "$path\n";

• automat:

S: ( 0, 0)                    
F: (A)                        
( 0, 0) -a> ( 1, 0)           
( 0, 0) -b> (-1, 0)           
( 0, 0) -c> ( 0, 1)           
( 0, 0) -d> ( 0,-1)
( 0, 0) -e> (A)

( 1, 0) -a> (F)
( 1, 0) -b> ( 0, 0)
( 1, 0) -c> ( 1, 1)
( 1, 0) -d> ( 1,-1)

(-1, 0) -a> ( 0, 0)
(-1, 0) -b> (F)
(-1, 0) -c> (-1, 1)
(-1, 0) -d> (-1,-1)

( 0, 1) -a> ( 1, 1)
( 0, 1) -b> (-1, 1)
( 0, 1) -c> (F)
( 0, 1) -d> ( 0, 0)

( 0,-1) -a> ( 1,-1)
( 0,-1) -b> (-1,-1)
( 0,-1) -c> ( 0, 0)
( 0,-1) -d> (F)

( 1, 1) -a> (F)
( 1, 1) -b> ( 0, 1)
( 1, 1) -c> (F)
( 1, 1) -d> ( 1, 0)

( 1,-1) -a> (F)
( 1,-1) -b> ( 0,-1)
( 1,-1) -c> ( 1, 0)
( 1,-1) -d> (F)

(-1, 1) -a> ( 0, 1)
(-1, 1) -b> (F)
(-1, 1) -c> (F)
(-1, 1) -d> (-1, 0)

(-1,-1) -a> ( 0,-1)
(-1,-1) -b> (F)
(-1,-1) -c> (-1, 0)
(-1,-1) -d> (F)