Ελαχιστοποίηση ΝΠΑ (Minimization)
Με την ελαχιστοποίηση μπορούμε να μειώσουμε τον αριθμό των κατασταστάσεων ενός ΝΠΑ στον ελάχιστο αριθμό.
Η μετατροπή ενός μη προσδιοριστικού αυτόματου, σε προσδιοριστικό, μπορεί να προκαλέσει εκθετική αύξηση του αριθμού των καταστάσεων, που στη συνέχεια πρέπει να περιοριστεί με την εφαρμογή ενός αλγορίθμου ελαχιστοποίησης.
Εχει θεμελιωθεί και θεωρητικά, ότι για δοθέν προσδιοριστικό αυτόματο, υπάρχει ένα μοναδικό ισοδύναμο αυτόματο με τον ελάχιστο αριθμό καταστάσεων.
Αποδεικνύεται (συνέπεια του Θεωρήματος Myhill-Nerode) ότι σε κάθε κανονικό σύνολο αντιστοιχεί ένα μοναδικό DFA με ελάχιστο αριθμό καταστάσεων και επιπλέον υπάρχει αλγόριθμος που κατασκευάζει το μοναδικό αυτό DFA. Ο αλγόριθμος αυτός βρίσκει συστηματικά όλα τα ζεύγη διακρίσιμων καταστάσεων όπως περιγράφεται παρακάτω:
Μπορούμε να βρούμε το ελάχιστο με τη μέθοδο Διαμέρισης ή με τη μέθοδο πίνακα (Myhill Nerode).
1. Μέθοδος Διαμέρισης (partitioning method)
Αρχή ισοδυναμίας (equivalence)
Σύμφωνα με την αρχή της ισοδυναμίας λέμε ότι δύο καταστάσεις Α και Β ενός αυτόματου είναι ισοδύναμες όταν ισχύει ένα από τα δύο παρακάτω.
δ(A, X) = F και δ(B, X) = F
ή
δ(A, X) ≠ F και δ(B, X) ≠ F
Όπου Χ είναι συμβολοσειρά και F μια τελική κατάσταση.
Ανάλογα με το μήκος της συμβολοσειράς X έχουμε ισοδυναμία βαθμού 0, 1, 2 κλπ.
Για παράδειγμα:
Αν |Χ| = 0 έχουμε ισοδυναμία 0, για |Χ| = 1 έχουμε ισοδυναμία 1 κλπ.
Πιο αυστηρά, δύο καταστάσεις qi και qj μπορούν να συγχωνευτούν αν:
∀w ∈ Σ* : δ(qi, w) ∈ F ⇔ δ(qj, w) ∈ F
Αλγόριθμος εύρεσης ελάχιστου ΝΠΑ
Για να βρούμε το ελάχιστο ακολουθούμε τον παρακάτω αλγόριθμο όπως αυτός φαίνεται στο παράδειγμα.
Έστω το παρακάτω αυτόματο με τελική κατάσταση το E:
Παράγουμε τον αντίστοιχο πίνακα καταστάσεων - μεταβάσεων.
q | 0 1 --------------------- start A | B C B | B D C | B C D | B E final E | B C
Αρχικοί έλεγχοι
1. Διαγράφουμε τις μη προσβάσιμες καταστάσεις (ή απρόσιτες) αν υπάρχουν.
2. Οι καταστάσεις καταβόθρας (trap, dead) ενώνονται σε μία αν υπάρχουν.
Βήμα 1
Χωρίζουμε τις καταστάσεις σε δύο σύνολα, ένα για τις τελικές καταστάσεις και ένα για τις μη τελικές.
{A, B, C, D} {E}
Βήμα 2
Για κάθε σύνολο ελέγχουμε τα στοιχεία ανά δύο για ισοδυναμία. Όπου δεν υπάρχει ισοδυναμία διασπάμε τα σύνολα.
Το αποτέλεσμα είναι το παρακάτω:
{A, B, C} {D} {E}
Εδώ το D το ξεχωρίσαμε γιατί ελεγχώμενο με το C βλέπουμε ότι για είσοδο 1 οι μεταβάσεις είναι στις καταστάσεις C και E οι οποίες όμως ανήκουν σε διαφορετικά σύνολα.
Βήμα 3
Επαναλαμβάνουμε την διαδικασία όπως παραπάνω από την αρχή για κάθε ένα σύνολο ξεχωριστά.
Το αποτέλεσμα είναι το παρακάτω:
{A, C} {B} {D} {E}
Βήμα 4
Επαναλαμβάνουμε την διαδικασία όπως παραπάνω για κάθε ένα σύνολο ξεχωριστά.
Το αποτέλεσμα είναι το παρακάτω:
{A, C} {B} {D} {E}
Ελέγχουμε για αλλαγή στα σύνολα και αν δεν υπάρχει θεωρούμε αυτό ως τελικό σχήμα (ελαχιστοποιημένο).
Και το νέο ελαχιστοποιημένο αυτόματο είναι το παρακάτω.
Να ελαχιστοποιηθεί το παρακάτω αυτόματο.
Σύμφωνα με το διάγραμμα ο πίνακας καταστάσεων μεταβάσεων είναι:
q | 0 1 -------------------- start A | B C B | A D final C | E F final D | E F final E | E F F | F F
Ελέγχουμε για απρόσιτες καταστάσεις και παγίδες.
Χωρίζουμε σε τελικές και μη τελικές καταστάσεις.
{A, B, F} {C, D, E}
Ελέγχουμε για ισοδυναμία στα δύο σύνολα.
{A, B} {F} {C, D, E}
Αυτή είναι η τελική μορφή και έτσι ο πίνακας είναι:
q | 0 1 ------------------------- start AB | AB CDE F | F F final CDE | CDE F
Και εδώ το αντίστοιχο διάγραμμα.
Να ελαχιστοποιηθεί το παρακάτω αυτόματο.
q | 0 1 ----------------- start A | B C final B | D E final C | E D D | G G E | G G F | D E final G | G G
Το αντίστοιχο διάγραμμα είναι:
Αφαιρούμε το F γιατί είναι απρόσιτο (φαίνεται και από τον πίνακα) και το τελικό σχήμα είναι:
Ακολουθούμε τον αλγόριθμο και οι διαδοχικές καταστάσεις είναι:
{A, D, E} {B, C, G}
{A, D, E} {B, C} {G}
{A} {D, E} {B, C} {G}
Άρα οι καταστάσεις που θα ενωθούν είναι: η D με την E και η B με την C.
Και το τελικό σχήμα είναι:
2. Μέθοδος πίνακα (Table filling method ή Myhill Nerode)
Με τη μέθοδο Myhill Nerode ακολουθούμε τα παρακάτω τρία βήματα:
- Σχεδιάζουμε πίνακα QxQ όπου Q ο αριθμός των καταστάσεων
- Διαγράφουμε τα διπλά κελιά. Δηλαδή για το (Α, Β) και (Β, Α) κρατάμε μόνο το (Α, Β)
- Τσεκάρουμε τα κελιά για τα αντίστοιχα ζεύγη όπου μια κατάσταση είναι τελική και μια μη τελική. Δηλαδή: Για το ζεύγος έστω (X, Y) θα πρέπει μία από τις δύο Χ ή Υ να είναι τελική κατάσταση και μία μη τελική π.χ.: (Χ∈F και Υ∉F) ή (Υ∈F και Χ∉F) όπου F τελική κατάσταση.
- Ελέγχουμε κάθε κενό κελί έστω (X, Y) και αν οι μεταβάσεις [δ(Χ, s), δ(Υ, s)] αντιστοιχούν σε τσεκαρισμένα κελιά, τότε τσεκάρουμε και το κελί ή ζεύγος (Χ, Υ).
- Σημειώνουμε τα ζεύγη που αντιστοιχούν σε μη τσεκαρισμένα κελιά.
- Αν έχουν προκύψει νέα ζεύγη, τότε επαναλαμβάνουμε πάλι για τα κενά κελιά.
- Συνδυάζουμε τα παραπάνω ζεύγη όπου υπάρχουν κοινές καταστάσεις και καταλήγουμε στο τελικό σχήμα.
Να ελαχιστοποιηθεί το παρακάτω αυτόματο με τη μέθοδο Myhill Nerode.
Βήμα 1,2: Δημιουργούμε τον πίνακα και διαγράφουμε τα διπλά κελιά.
Βήμα 3: Τσεκάρουμε τα κελιά σύμφωνα με τον κανόνα στο βήμα 3.
Βήμα 4: Κάνουμε τους σχετικούς ελέγχους για τα κενά κελιά.
(B, A) δ(B, 0) = A, δ(B, 1) = D
δ(A, 0) = B, δ(A, 1) = C
Επειδή τα (B, A) και (D, C) είναι κενά δεν αλλάζουμε κάτι.
(D, C) δ(D, 0) = E, δ(D, 1) = F
δ(C, 0) = E, δ(C, 1) = F
(E, C) δ(E, 0) = E, δ(E, 1) = F
δ(C, 0) = E, δ(C, 1) = F
(E, D) δ(E, 0) = E, δ(E, 1) = F
δ(D, 0) = E, δ(D, 1) = F
(F, A) δ(F, 0) = F, δ(F, 1) = F
δ(A, 0) = B, δ(A, 1) = C
Επειδή το (F, C) είναι τσεκαρισμένο πρέπει να τσεκαριστεί και το (F, A).
(F, B) δ(F, 0) = F, δ(F, 1) = F
δ(B, 0) = A, δ(B, 1) = D
Επειδή το (F, A) είναι τσεκαρισμένο πρέπει να τσεκαριστεί και το (F, B).
Επειδή στον πρώτο έλεγχο προέκυψαν νέα ζεύγη, επαναλαμβάνουμε τη διαδικασία για τα κενά κελιά.
Από τη νέα διαδικασία δεν προκύπτουν νέα τσεκαρισμένα κελιά άρα εδώ σταματάμε.
Και καταλήγουμε στον τελικό πίνακα που είναι ο παρακάτω.
Βήμα 5: Τα ζεύγη που αντιστοιχούν σε κενά κελιά είναι:
(B, A), (D, C), (E, C), (E, D)
Βήμα 6: Επειδή τα ζεύγη (D, C), (E, C), (E, D) έχουν κοινές καταστάσεις τα ενώσουμε σε μία κατάσταση CDE. Άρα οι τελικές καταστάσεις είναι:
AB, CDE και F
Ο πίνακας είναι:
q 0 | 1
------------------------
start AB AB | CDE
F F | F
final CDE CDE | F
Και το τελικό διάγραμμα είναι:
Να βρεθεί το ελάχιστο για το παρακάτω αυτόματο με τη μέθοδο Myhill Nerode
A B C D E A B[ ] C[ ][ ] D[ ][ ][ ] E[X][X][X][X] ================ B->0->B B->1->D A->0->B A->1->C C->0->B C->1->C A->0->B A->1->C C->0->B C->1->C B->0->B B->1->D D->0->B D->1->E A->0->B A->1->C D->0->B D->1->E B->0->B B->1->D D->0->B D->1->E C->0->B C->1->C A B C D E A B[ ] C[ ][ ] D[X][X][X] E[X][X][X][X] ================ B->0->B B->1->D A->0->B A->1->C C->0->B C->1->C A->0->B A->1->C C->0->B C->1->C B->0->B B->1->D A B C D E A B[X] C[ ][X] D[X][X][X] E[X][X][X][X]
Το ζεύγος που θα ενωθεί είναι το (A, C)
Ο αντίστοιχος πίνακας είναι
Q 0 1 ----------------- AC B AC B B D D B E E B AC
Επαλήθευση με την πρώτη μέθοδο
{A, B, C, D} {E}
{A, B, C} {D} {E}
{A, C} {B} {D} {E}
{A, C} {B} {D} {E}