5.9 Τρ, 5/11/02: Ελαχιστοποίηση DFA

Το ερώτημα που μας απασχολεί εδώ είναι πώς, δοθέντος ενός DFA $M$, να βρούμε ένα άλλο DFA, έστω $N$, που να είναι ισοδύναμο με το $M$ (δηλ. $L(M) = L(N)$ - αναγνρίζουν την ίδια γλώσσα) και να έχει τον ελάχιστο αριθμό καταστάσεων.

Εξετάζοντας την απόδειξη του θεωρήματος Myhill-Nerode βλέπει κανείς εύκολα ότι υπάρχει ουσιαστικά ένα μοναδικό τέτοιο ελάχιστο DFA, και είναι αυτό που ως σύνολο καταστάσεών του έχει το σύνολο των κλάσεων ισοδυναμίας της δεξιά αναλλοίωτης σχέσης ισοδυναμίας $R_L$, με $L = L(M)$, και ως συνάρτηση μετάβασης τη συνάρτηση $\delta([x],\alpha) = [x\alpha]$ (δείτε την απόδειξη του Θεωρήματος Myhill-Nerode) όπου $[x]$ συμβολίζει την κλάση της λέξης $x \in \Sigma^*$ και $\alpha\in\Sigma$. Είδαμε επίσης στην απόδειξη του θεωρήματος Myhill-Nerode ότι οι κλάσεις της σχέσης $R_M$ είναι υποσύνολα των κλάσεων της $R_L$, και αυτό σημαίνει ότι, όποιο και να είναι το DFA $M$, το ελάχιστο αυτόματο μπορεί να προκύψει από το $M$ αν όλες οι κορυφές του $M$ που είναι $R_L$ ισοδύναμες συμπτυχθούν σε μία κορυφή, ώστε πλέον να μην υπάρχουν στο νέο αυτόματο δύο ή περισσότερες κορυφές, που η κλάσεις τους να είναι $R_L$ ισοδύναμες.

Η μέθοδος ελαχιστοποίησης λοιπόν αποφασίζει για το ποιες θα είναι οι καταστάσεις του ελάχιστου DFA αφού βρεί, για κάθε ζεύγος κορυφών του $M$, αν οι καταστάσεις αυτές είναι μεταξύ τους $R_L$-ισοδύναμες. Οι καταστάσεις του ελάχιστου αυτομάτου θα είναι τα σύνολα $R_L$-ισοδυνάμων κορυφών του $M$. Για να υπολογίσουμε για κάθε ζεύγος κορυφών $u$ και $v$ του $M$ αν είναι $R_L$-ισοδύναμες θεωρούμε κατ' αρχήν όλα τα ζεύγη κορυφών ισοδύναμα και αν προκύψει για ένα ζεύγος κορυφών ότι δεν είναι τότε μόνο τις χωρίζουμε.

Έτσι, θέλουμε να υπολογίσουμε μια συνάρτηση $f(u,v)$ όπου $u$ και $v$ είναι δύο οποιεσδήποτε διαφορετικές κορυφές του $M$, και θέλουμε η συνάρτηση αυτή να κάνει 1 αν οι $u$ και $v$ ΔΕΝ είναι ισοδύναμες και 0 αν είναι. Κατ' αρχήν λοιπόν δίνουμε τις αρχικές τιμές,

$$\forall u,v\in Q, u\neq v,    f(u,v)=0,$$ (9)

όπου $Q$ το σύνολο των κορυφών του $M$.

Σύμφωνα με τον ορισμό της σχέσης ισοδυναμίας $R_L$ δύο λέξεις $x$ και $y$ είναι μεταξύ τους $R_L$-ισοδύναμες αν όποια και να είναι η λέξη $z$ είτε και οι δύο λέξεις $xz$, $yz$ ανήκουν στην $L$ είτε κι οι δύο δεν ανήκουν. Αμέσως αυτό μας δίνει (με επιλογή $z = \epsilon$) ότι αν $u\in F$ και $v \notin F$ τότε οι $u$ και $v$ δεν είναι ισοδύναμες. Αυτό μας δίνει το επόμενο βήμα του αλγορίθμου μας

$$\forall u \in F, v \notin F   f(u,v)=1.$$ (10)

Είναι επίσης φανερό από τον ορισμό της $R_L$ ότι αν για τις κορυφές $u$ και $v$ γνωρίζουμε ήδη ότι δεν είναι ισοδύναμες, και για τις δύο κορυφές $a$ και $b$ υπάρχει μια λέξη $\sigma$ τέτοια ώστε $u = \delta(a, \sigma)$ και $v = \delta(b, \sigma)$ τότε και οι $a$, $b$ δεν είναι μεταξύ τους $R_L$-ισοδύναμες. Αυτή η παρατήρηση μας δίνει τον υπόλοιπο αλγόριθμο: Ορίζουμε κατ' αρχήν το σύνολο $S$ από ζεύγη κορυφών να περιέχει όλα τα ζεύγη κορυφών $(u,v)$ με $u\in F$, $v \notin F$, δηλ. όλα τα ζεύγη κορυφών για τα οποία γνωρίζουμε ότι τα μέλη τους δεν είναι ισοδύναμα. Έστω τώρα ένα νέο σύνολο κορυφών $T$ που αποτελείται από όλα τα ζεύγη κορυφών $(a,b)$ για τα οποία ισχύει ακόμη $f(a,b)=0$ (θεωρούνται δηλ. ακόμη ισοδύναμα) και για τα οποία υπάρχει ένα γράμμα $\sigma\in\Sigma$ τέτοιο ώστε το ζεύγος

$$(\delta(a,\sigma), \delta(b,\sigma)) \in S.$$

Αφού υπολογίσουμε το σύνολο αυτό $T$ θέτουμε μετά $f(a,b)=1$ για όλα τα $(a,b) \in T$, και τέλος αντιγράφουμε το $T$ πάνω στο παλιό $S$, το οποίο και πετάμε, και συνεχίζουμε την ίδια διαδικασία (φτιάχνουμε ένα νέο $T$ που προκύπτει από το νέο $S$, κ.ο.κ.), έως ότου το σύνολο $T$ που φτιάξουμε να προκύψει κενό. Αυτό σηματοδοτεί ότι δεν έχουμε πλέον άλλη πληροφορία να αντλήσουμε και σταματάμε εδώ.

Αποδεικνύεται ότι ο αλγόριθμος αυτός δουλεύει, δηλ. όταν σταματήσει έχουμε $f(u,v)=1$ ακριβώς για εκείνα τα ζεύγη κορυφών $(u,v)$ με μη $R_L$-ισοδύναμα μέλη.

Η κατασκευή του ελάχιστου αυτομάτου γίνεται τώρα όπως στην απόδειξη του θεωρήματος Myhill-Nerode: βάζουμε από μιά κορυφή για κάθε ομάδα ισοδυνάμων κορυφών του $M$. Για να βρούμε που θα πάμε με το γράμμα $\alpha$ από μια τέτοια ``υπερκορυφή'' επιλέγουμε μια οποιαδήποτε $M$-κορυφή της υπερκορυφής αυτής και βλέπουμε που μας πάει το $\alpha$ αν ξεκινήσουμε από αυτή την κορυφή στο παλιό μας αυτόματο $M$. Η $M$-κορυφή όου καταλήγουμε ανήκει σε μια υπερκορυφή του νέου μας υπό κατασκευή αυτομάτου και σε αυτή πρέπει να μεταβούμε. Μια υπερκορυφή θεωρείται τελική αν περιέχει κάποια τελική κορυφή του $M$ (αναγκαστικά τότε θα περιέχει μόνο τελικές κορυφές του $F$) ενώ η αρχική υπερκορυφή είναι αυτή που περιέχει την αρχική κορυφή του $M$.