7.4 Ισοδυναμία NFA και DFA.

Επαναλαμβάνουμε ότι για ένα NFA η συνάρτηση μετάβασης $\delta$ είναι ο τρόπος κωδικοποίησης των μεταβάσεων του. Αν δηλ. $q\in Q$ είναι μια κατάσταση και $\alpha\in\Sigma$ είναι ένα γράμμα του αλφαβήτου, το σύνολο $\delta(q,\alpha)\subseteq Q$ είναι το σύνολο όλων των καταστάσεων του NFA στις οποίες μπορεί αυτό να μεταβεί όντας στην κατάσταση $q$ και διαβάζοντας το γράμμα $\alpha$.

Ορισμός 7.11   (Η συνάρτηση $\delta$ πάνω σε σύνολα) Αν $A \subseteq Q$ είναι ένα σύνολο καταστάσεων και $B \subseteq \Sigma$ είναι ένα σύνολο γραμμάτων τότε

$$\delta(A,B) = \bigcup_{q \in A, \alpha \in B} \delta(q,\alpha).$$

Δηλ. $\delta(A,B)$ είναι το σύνολο όλων των καταστάσεων στις οποίες μπορεί κανείς να φτάσει ξεκινώντας από κάποια κατάσταση του $A$ και ακολουθώντας κάποιο γράμμα $\alpha$ του συνόλου $B$. Η επέκταση αυτή της συνάρτησης $\delta$ ώστε να παίρνει ως όρισμα σύνολα αντί για γράμματα είναι η συνηθισμένη επεκταση μιας συνάρτησης $f:C\to D$ που με $f(X)$, $X\subseteq C$, συμβολίζει το σύνολο εικόνων του συνόλου $X$ μέσω της $f$.

Επεκτείνουμε τώρα το πεδίο ορισμού της συνάρτησης $\delta$ όσον αφορά το δεύτερο όρισμά της.

Ορισμός 7.12   (Η συνάρτηση μετάβασης $\delta$ πάνω σε λέξεις) Αν $q\in Q$ είναι μια κατάσταση και $w \in \Sigma^*$ είναι μια λέξη (ενδεχομένως και κενή) τότε ορίζουμε το σύνολο καταστάσεων $\delta(q, w)$ ως εξής:

$$\delta(q, w) = \left\{ \begin{array}{ll} {\left\{{q}\right\}} & \... ...psilon\alpha\nu    w=v\alpha, v\in\Sigma^*, \alpha\in\Sigma. \end{array}\right.$$ (7.1)

Παρατήρηση 7.6   Ο ορισμός (7.1) απαιτεί λίγη προσοχή όσον αφορά το δεύτερο σκέλος του μια και είναι αυτοαναφορικός, αναφερόμαστε δηλ. στη συνάρτηση $\delta$ για να ορίσουμε τη συνάρτηση $\delta$. Η ουσία εδώ είναι ότι αυτή η αυτοαναφορά δε δημιουργεί κάποιο πρόβλημα, μια και για να ορίσουμε το $\delta(q, w)$ αναφερόμαστε σε τιμές του $\delta(q, x)$ για λέξεις $x$ με μήκος ${\left\vert{x}\right\vert} < {\left\vert{w}\right\vert}$, και υπάρχει και ο ξεχωριστός ορισμός για τη λέξη μήκους 0 όπου σταματά η αυτοαναφορά. Για να υπολογιστεί έτσι το $\delta(q, w)$ υπολογίζεται πρώτα το $\delta$ για ολοένα και μικρότερες λέξεις, ώσπου τελικά φτάνει να χρησιμοποιείται το πρώτο μέλος του ορισμού (7.1) που δεν έχει αυτοαναφορά. Για παράδειγμα, αν θέλει κανείς να υπολογίσει την τιμή $\delta(q,abc)$, όπου $a,b,c\in\Sigma$, ακολουθώντας τον ορισμό (7.1) αυτό γίνεται ως εξής:

$$\delta(q, abc) = \delta( \delta(q, ab), c)$$

$$= \delta( \delta( \delta(q, a), b), c).$$

Παρατηρούμε ότι στην τελευταία γραμμή η συνάρτηση $\delta$ είναι η γνωστή μας συνάρτηση που σαν δεύτερο όρισμα έχει σύμβολο του αλφαβήτου και όχι λέξη. Ορισμοί όπως ο (7.1) είναι πολύ κοινοί και ονομάζονται αναδρομικοί.

Με άλλα λόγια $\delta(q, w), w\in\Sigma^*$, είναι το σύνολο όλων εκείνων των καταστάσεων του αυτομάτου στις οποίες μπορεί κανείς να βρεθεί ξεκινώντας από την κατάσταση $q$ και ακολουθώντας τη λέξη $w$. Και, αν $R \subseteq Q$ είναι ένα σύνολο καταστάσεων, με $\delta(R, w)$ συμβολίζεται το σύνολο όλων των καταστάσεων στις οποίες μπορεί κανείς να πάει ξεκινώντας από κάποια κατάσταση στο $R$ και ακολουθώντας τη λέξη $w$.

Παρατήρηση 7.7   Μια λέξη $w$ αναγνωρίζεται από ένα αυτόματο αν και μόνο αν

$$\delta(q_0, w) \cap F \neq \emptyset,$$

όπου $F$ το σύνολο των τελικών καταστάσεων του NFA. Αναγνωρίζεται δηλ. μια λέξη αν και μόνο αν είναι δυνατή η μετάβαση από την αρχική σε κάποια τελική κατάσταση ακολουθώντας τη λέξη.

Ορισμός 7.13   (Ισοδυναμία αυτομάτων) Δύο ντετερμινιστικά ή μη ντετερμινιστικά αυτόματα $M_1$ και $M_2$ λέγονται ισοδύναμα αν και μόνο αν $L(M_1) = L(M_2)$, αν αναγνωρίζουν δηλ. ακριβώς τις ίδιες λέξεις.

Θεώρημα 7.1   (Ισοδυναμία NFA και DFA) Για κάθε NFA $M$ υπάρχει ισοδύναμο DFA $M'$.

Απόδειξη. Περιγράφουμε ένα αλγόριθμο μετάβασης από ένα τυχόν NFA $M$ σε ένα ισοδύναμο DFA $M'$.

Έστω λοιπόν ότι το NFA $M$ είναι η πεντάδα $(Q,\Sigma,\delta,q_0,F)$. Το DFA $M' = (Q',\Sigma,\delta',q_0',F')$ θα έχει σύνολο καταστάσεων $Q' = 2^Q$ το δυναμοσύνολο (σύνολο όλων των υποσυνόλων) του $Q$, αρχική κατάσταση $q_0' = {\left\{{q_0}\right\}}$, ίδιο αλφάβητο $\Sigma$ και τελικές καταστάσεις όλα εκείνα τα σύνολα καταστάσεων του $M$ που περιέχουν κάποια τελική κατάσταση

$$F' = {\left\{{A \subseteq Q: A \cap F \neq \emptyset}\right\}}.$$

Τέλος η συνάρτηση μετάβασης $\delta':Q'\times\Sigma\to Q'$ του $M'$ ορίζεται ως

$$\delta'(q', \alpha) = \delta(q', \alpha).$$

Θυμηθείτε ότι το σύμβολο $q'$ παριστάνει μια κατάσταση του $M'$ άρα ένα σύνολο καταστάσεων του $M$, και άρα η $\delta$ συνάρτηση που εμφανίζεται δεξιά στον άνω ορισμό είναι η επεκτεταμένη $\delta$ συνάρτηση του αυτομάτου $M$ όπως την ορίσαμε παραπάνω, μια και σαν πρώτο όρισμα έχει ολόκληρο σύνολο.

Με άλλα λόγια: στο DFA $M'$ που κατασκευάζουμε από την κατάσταση $q_1$ (υποσύνολο του $Q$) με το σύμβολο $\alpha\in\Sigma$ μεταβαίνουμε στην κατάσταση $q_2$, που είναι το σύνολο όλων εκείνων των καταστάσεων του $M$ στις οποίες μπορούμε να μεταβούμε από κάποια κατάσταση του συνόλου $q_1$ με το γράμμα $\alpha$ κινούμενοι πάνω στο $M$. Δείτε το Παράδειγμα 7.21 παρακάτω.

Άσκηση 7.18   Αποδείξτε με επαγωγή ως προς το μήκος ${\left\vert{w}\right\vert}$ της λέξης $w \in \Sigma^*$ ότι για κάθε κατάσταση $q$ του $M'$ ισχύει

$$\delta'(q, w) = \delta(q, w).$$

Για να δείξουμε το Θεώρημα αρκεί να δείξουμε την ισοδυναμία

$$w \in L(M) \Longleftrightarrow w \in L(M')$$ (7.2)

για όλες τις λέξεις $w \in \Sigma^*$. Αλλά $w\in L(M)$ αν και μόνο αν $\delta(q_0,w) \in F$, ενώ $w \in L(M')$ αν και μόνο αν $\delta'(q_0',w) \in F'$. Χρησιμοποιώντας την Άσκηση 7.18 το τελευταίο συμβαίνει αν και μόνο αν $\delta({\left\{{q_0}\right\}},w) \in F'$ και, χρησιμοποιώντας τον ορισμό του $F'$ βλέπουμε ότι αυτό ισχύει αν και μόνο αν $\delta(q_0, w) \cap F \neq \emptyset$. Όμως το σύνολο $\delta(q_0,w)$ είναι μονοσύνολο μια και το $M$ είναι DFA, άρα η τελευταία συνθήκη είναι ισοδύναμη με $\delta(q_0,w) \in F$, και η απόδειξη είναι πλήρης. $\qedsymbol$

Παράδειγμα 7.21   Ας δούμε τώρα πώς μετατρέπεται το ακόλουθο απλό NFA του Σχήματος 7.8 σε DFA. Το αποτέλεσμα δίνεται στο Σχήμα 7.9.

Σχήμα 7.8: $M$, ένα απλό NFA

Το σύνολο καταστάσεων του $M'$ θα είναι το δυναμοσύνολο του συνόλου καταστάσεων του $M$ δηλ. του ${\left\{{A,B}\right\}}$. Είναι δηλ. το σύνολο

$$Q' = {\left\{{ X={\left\{{A}\right\}}, Y={\left\{{B}\right\}}, Z={\left\{{A,B}\right\}}, W=\emptyset }\right\}}.$$

Σύνολο τελικών καταστασεων είναι το $F' = {\left\{{Y, Z}\right\}}$, όλα εκείνα τα σύνολα δηλ. που περιέχουν κάποια τελική κατάσταση του $M$. Αρχική κατάσταση είναι η $X$.

Σχήμα 7.9: Το NFA $M$ του Σχήματος 7.8 μετετράπη στο DFA $M'$

Άσκηση 7.19   Ελέγξτε την ορθότητα την ισοδυναμίας του NFA του σχήματος 7.8 στο DFA του σχήματος 7.9, πάνω στις λέξεις $001$ και $10$.

Άσκηση 7.20   Φτιάξτε ισοδύναμα DFA για τα NFA

1. $(Q = {\left\{{p, q, r, s}\right\}}, \Sigma = {\left\{{0,1}\right\}}, \delta_1, q_0 = p, F = {\left\{{s}\right\}})$
2. $(Q = {\left\{{p, q, r, s}\right\}}, \Sigma = {\left\{{0,1}\right\}}, \delta_2, q_0 = p, F = {\left\{{q, s}\right\}})$

όπου οι συναρτήσεις μετάβασης είναι οι

$$\delta_1: \ \begin{array}{l\vert r\vert r} & 0 & 1 \\ \... ...p}\right\}}\\ s & \emptyset & {\left\{{p}\right\}} \end{array}$$

Άσκηση 7.21   Αν ένα NFA έχει $n$ σε πλήθος καταστάσεις, πόσες το πολύ καταστάσεις χρειάζεται να έχει ένα ισοδύναμό του DFA;