5.5 Τρ, 8/10/02: Ισοδυναμία NFA και DFA. NFA με $\epsilon$-κινήσεις

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

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

$$\delta(R, \alpha) = \bigcup_{q \in R} \delta(q, \alpha),$$

όπου $R \subseteq Q$ και $\alpha\in\Sigma$. Με λόγια, $\delta(R, \alpha)$ είναι το σύνολο όλων των καταστάσεων στις οποίες μπορεί κανείς να φτάσει ακολουθώντας κάποια $\alpha$-ακμή (ακμή δηλ. με ετικέτα $\alpha$) και ξεκινώντας από κάποια κατάσταση στο σύνολο καταστάσεων $R$.

Επεκτείνουμε τώρα το πεδίο ορισμού της συνάρτησης $\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.$$ (3)

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

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

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

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

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

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

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

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

Είμαστε τώρα σε θέση να περιγράψουμε τον αλγόριθμο μετάβασης από ένα τυχόν 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$.

Ας δούμε τώρα πώς μετατρέπεται το ακόλουθο απλό NFA του Σχήματος 10 σε DFA. Το αποτέλεσμα δίνεται στο Σχήμα 11.

Σχήμα 10. $M$, ένα απλό NFA

Το σύνολο καταστάσεων του $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$.

Σχήμα 11. Το NFA $M$ του Σχήματος 10 μετατετραμμένο στο DFA $M'$

Δε θα δώσουμε εδώ την απλή επαγωγική (ως προς το μήκος της λέξης $w$) απόδειξη του ότι η διαδικασία που περιγράψαμε παράγει ένα DFA $Μ'$ ισοδύναμο με το δοθέν NFA $M$, δηλ. τέτοιο ώστε η λέξη $w$ γίνεται αποδεκτή από το DFA $M'$ αν και μόνο αν γίνεται από το NFA $M$.

Άσκηση 5.5.1   Φτιάξτε ισοδύναμα 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 \\ ... ...}\right\}}\\ s & \emptyset & {\left\{{p}\right\}} \end{array}$$

5.5.2 NFA με $\epsilon$-κινήσεις

Μια ακόμη παραλλαγή του μοντέλου του πεπερασμένου αυτομάτου είναι το μη ντετερμινιστικό αυτόματο με $\epsilon$-κινήσεις. Αυτό είναι ένα NFA που έχει, ενδεχομένως, και κάποιες ακμές που αντί να έχουν ως ετικέτα ένα γράμμα του αλφαβήτου έχουν την κενή λέξη $\epsilon$. Ας τα λέμε αυτά $\epsilon$-NFA.

Το νόημα μιας $\epsilon$-ακμής από μια κορυφή $q_1$ σε μια κορυφή $q_2$ είναι το εξής: αν το NFA βρίσκεται στην κατάσταση $q_1$ τότε μπορεί να επιλέξει να μεταβεί στην κατάσταση $q_2$ χωρίς να διαβάσει το επόμενο γράμμα της λέξης. Το παρακάτω $\epsilon$-NFA αναγνωρίζει τη γλώσσα $0^*1^*2^*$, για παράδειγμα:

Σχήμα 12. Ένα $\epsilon$-NFA για τη γλώσσα $0^*1^*2^*$.

Πώς αναγνωρίζει το αυτόματο του Σχήματος 12 τη λέξη $0^21^32^5$; Κάνει δύο μεταβάσεις από την πρώτη κορυφή στον εαυτό της διαβάζοντας τα δύο 0, μετά μεταβαίνει στη δεύτερη κορυφή χωρίς να διαβάσει τίποτα, μεταβαίνει από τη δεύτερη κορυφή στον εαυτό της τρεις φορές διαβάζοντας τα 1, μεταβαίνει στην τρίτη κορυφή χωρίς πάλι να διαβάσει τίποτα, και τέλος μεταβαίνει από την τρίτη κορυφή στον εαυτό της διαβάζοντας τα πέντε 2.

Αποδεικνύεται (αλλά παραλείπουμε την απόδειξη) ότι τα $\epsilon$-NFA είναι ισοδύναμα με τα NFA, και άρα και με τα DFA. Για κάθε $\epsilon$-NFA δηλ. υπάρχει ένα NFA χωρίς $\epsilon$-κινήσεις που αναγνωρίζει την ίδια γλώσσα. Για να μεταβούμε από ένα $\epsilon$-NFA $M$ σε ένα ισοδύναμο NFA $M'$ κάνουμε τα εξής:

• Αφήνουμε το ίδιο σύνολο καταστάσεων.
• Προσθέτουμε στις τελικές καταστάσεις $F$ όλες εκείνες τις καταστάσεις που συνδέονται με κάποια κορυφή του $F$ με ένα $\epsilon$-μονοπάτι, μια ακολουθία δηλ. $\epsilon$-ακμών.
• Για κάθε κατάσταση $q$ και γράμμα $\alpha$ του $\Sigma$ θέτουμε ως $\delta(q,\alpha)$ το σύνολο όλων των καταστάσεων στις οποίες μπορεί κανείς να μεταβεί από την $q$ διανύοντας πρώτα κάποιες (ενδεχομένως και καμία) $\epsilon$-ακμές, μετά μια $\alpha$-ακμή και τέλος κάποιες (ενδεχομένως και καμία) $\epsilon$-ακμές.
• Σβήνουμε όλες τις $\epsilon$-κινήσεις

Έτσι το $\epsilon$-NFA του Σχήματος 12 γίνεται:

Σχήμα 13. Το $\epsilon$-NFA του Σχήματος 12 μετατετραμμένο σε NFA