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$ είναι ένα σύνολο γραμμάτων τότε

$\displaystyle \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)$ ως εξής:

$\displaystyle \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) αυτό γίνεται ως εξής:
$\displaystyle \delta(q, abc)$ $\displaystyle =$ $\displaystyle \delta( \delta(q, ab), c)$  
  $\displaystyle =$ $\displaystyle \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$ αναγνωρίζεται από ένα αυτόματο αν και μόνο αν

$\displaystyle \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$ που περιέχουν κάποια τελική κατάσταση

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

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

$\displaystyle \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'$ ισχύει

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

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

$\displaystyle 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\}}$. Είναι δηλ. το σύνολο

$\displaystyle 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\}})$
όπου οι συναρτήσεις μετάβασης είναι οι

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

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

Mihalis Kolountzakis 2015-11-28