Μετατροπή NFA σε DFA

Θα δούμε πώς να μετατρέψουμε ένα μη ντετερμινιστικό αυτόματο σε ντετερμινιστικό αυτόματο, αποδεικνύοντας έτσι ότι η υπολογιστική ισχύς των μη ντετερμινιστικών και των ντετερμινιστικών αυτομάτων είναι ισοδύναμη.

Βασική ιδέα

Έστω ένα μη ντετερμινιστικό αυτόματο ⟨Q_N, Σ_N, δ_N, q₀, F_N⟩ χωρίς ε-μεταβάσεις. Κατασκευάζουμε ένα ντετερμινιστικό αυτόματο ⟨Q_D, Σ_D, δ_D, p₀, F_D⟩ ως εξής:

• Q_D ⊆ 2^Q_N
• Σ_D = Σ_N
• p₀ = {q₀}
• F_D = {Q ∈ Q_D ∣ Q ∩ F_N ≠ ∅}

Τη συνάρτηση μετάβασης δ_D ορίζουμε ως εξής:

$$\mathrm{\forall }Q\in Q_D,a\in {\mathrm{\Sigma }}_D:{\delta }_D(Q,a)=\bigcup _{q\in Q}{\delta }_N(q,a)$$

Τι σημαίνει αυτό; Ένα μη ντετερμινιστικό αυτόματο μπορεί να βρίσκεται ταυτόχρονα σε περισσότερες καταστάσεις, οπότε μπορεί π.χ. να βρεθούμε στην περίπτωση όπου το μη ντετερμινιστικό αυτόματό μας είναι στις καταστάσεις {q₀, q₁}. Διαβάζοντας το επόμενο σύμβολο, για παράδειγμα το 1, μπορούμε να φτάσουμε στο σύνολο καταστάσεων {q₀, q₂, q₃}. Στην ντετερμινιστική εκδοχή του ίδιου αυτομάτου αυτό εκφράζεται ως εξής: δημιουργούμε δύο καταστάσεις, τις ονομάζουμε {q₀, q₁} και {q₀, q₂, q₃} και βάζουμε ανάμεσά τους μετάβαση για το σύμβολο 1. Τυπικά πηγαίνουμε από τη μία κατάσταση στην άλλη, αλλά χάρη στην ονομασία θα ξέρουμε ότι στο μη ντετερμινιστικό αυτόματο θα βρισκόμασταν σε δύο και σε τρεις καταστάσεις αντίστοιχα.

Παράδειγμα

Έστω αυτό το μη ντετερμινιστικό αυτόματο:

Για να κατασκευάσουμε το ντετερμινιστικό αυτόματο, χρειαζόμαστε πρώτα απ' όλα μια νέα συνάρτηση μετάβασης. Θα μας βοηθήσει ένας πίνακας, στον οποίο θα γράψουμε όλες τις μεταβάσεις. Στην αρχή ο πίνακας έχει ως εξής:

$$\begin{array}{ccc}\text{κατάσταση}/\text{σύμβολο}& 0& 1\\ \left\{q_0\right\}\end{array}$$

Στην αριστερή στήλη θα έχουμε στο τέλος του αλγορίθμου όλες τις καταστάσεις του ντετερμινιστικού αυτομάτου. Ο συμπληρωμένος πίνακας θα ορίζει τότε τη συνάρτηση μετάβασης. Τώρα γράφουμε στον πίνακα σε ποιες καταστάσεις πηγαίνουμε, αν βρισκόμαστε στις καταστάσεις {q₀} και στην είσοδο είναι τα σύμβολα 0 και 1.

$$\begin{array}{ccc}\text{κατάσταση}/\text{σύμβολο}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\end{array}$$

Από την κατάσταση q₀ οδηγεί για το σύμβολο 0 μετάβαση μόνο στην κατάσταση q₁, ενώ για το σύμβολο 1 οδηγεί στις καταστάσεις q₁ και q₂. Τώρα προσθέτουμε στον πίνακα δύο νέες καταστάσεις: {q₁} και {q₁, q₂}. Γιατί; Όποτε συμπληρώνουμε στον πίνακα ένα σύνολο καταστάσεων που δεν έχουμε ακόμη στην αριστερή στήλη, το προσθέτουμε εκεί.

$$\begin{array}{ccc}\text{κατάσταση}/\text{σύμβολο}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \left\{q_1\right\}\\ \{q_1,q_2\}\end{array}$$

και πάλι συμπληρώνουμε. Για την κατάσταση {q₁, q₂} δεν πρέπει να ξεχάσουμε να ελέγξουμε και τις δύο καταστάσεις, δηλαδή πού πηγαίνουμε από την κατάσταση q₁ ενωμένο με το πού πηγαίνουμε από την κατάσταση q₂.

$$\begin{array}{ccc}\text{κατάσταση}/\text{σύμβολο}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \left\{q_1\right\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_1,q_2\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\end{array}$$

Πήραμε μερικές νέες καταστάσεις, που πρέπει να προσθέσουμε στον πίνακα:

$$\begin{array}{ccc}\text{κατάσταση}/\text{σύμβολο}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \left\{q_1\right\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_1,q_2\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_0,q_1,q_3\}\\ \{q_0,q_3\}\end{array}$$

…και πάλι συμπληρώνουμε τις μεταβάσεις:

$$\begin{array}{ccc}\text{κατάσταση}/\text{σύμβολο}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \left\{q_1\right\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_1,q_2\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_0,q_1,q_3\}& \{q_0,q_1,q_3\}& \{q_0,q_1,q_2,q_3\}\\ \{q_0,q_3\}& \left\{q_1\right\}& \{q_1,q_2\}\end{array}$$

Οι καταστάσεις {q₀, q₁, q₃}, {q₁} και {q₁,q₂} υπάρχουν ήδη, οπότε προσθέτουμε μόνο την κατάσταση {q₀,q₁,q₂,q₃}.

$$\begin{array}{ccc}\text{κατάσταση}/\text{σύμβολο}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \left\{q_1\right\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_1,q_2\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_0,q_1,q_3\}& \{q_0,q_1,q_3\}& \{q_0,q_1,q_2,q_3\}\\ \{q_0,q_3\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \{q_0,q_1,q_2,q_3\}& \{q_0,q_1,q_3\}& \{q_0,q_1,q_2,q_3\}\end{array}$$

Δεν προσθέσαμε καμία νέα κατάσταση, άρα ο πίνακας είναι συμπληρωμένος. Τώρα απλώς σχεδιάζουμε το διάγραμμα. Οι καταστάσεις του ντετερμινιστικού αυτομάτου είναι στην πρώτη στήλη, οι μεταβάσεις για τα σύμβολα 0 και 1 στις επόμενες. Κάθε κατάσταση που περιέχει κάποια τελική κατάσταση του αρχικού αυτομάτου θα είναι τελική και σε αυτό το αυτόματο. Δηλαδή κάθε κατάσταση που περιέχει την q₃ θα είναι τελική. Το αυτόματο θα φαίνεται ως εξής:

Μπορούμε να δείξουμε ότι το αυτόματο λειτουργεί πραγματικά σωστά. Ας δοκιμάσουμε αν το αυτόματο αποδέχεται τη λέξη 11001. Στο ντετερμινιστικό αυτόματο θα ακολουθήσουμε τη διαδρομή

$$q_0{\to }^1{q}_1,q_2{\to }^1{q}_0,q_3{\to }^0{q}_1{\to }^0{q}_0,q_1,q_3{\to }^1{q}_0,q_1,q_2,q_3$$

και το αυτόματο θα αποδεχόταν τη λέξη, επειδή η τελευταία κατάσταση {q₀, q₁, q₂, q₃} είναι τελική. Στο μη ντετερμινιστικό αυτόματο, κατά την προσομοίωση, θα φτάναμε στις ίδιες καταστάσεις, δηλαδή θα ξεκινούσαμε από την κατάσταση q₀ και για το σύμβολο 1 θα φτάναμε στις καταστάσεις {q₁, q₂}. Το επόμενο σύμβολο 1 θα μας έφερνε στις καταστάσεις {q₀,q₃} κ.ο.κ. για τις υπόλοιπες καταστάσεις. Στο τέλος θα βρισκόμασταν σε όλες τις καταστάσεις {q₀, q₁, q₂, q₃} και το αυτόματο θα αποδεχόταν τη λέξη.

Πηγές

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools