Προσομοίωση μη ντετερμινιστικού αυτομάτου

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

Η αρχή του αλγορίθμου

Την αρχή θα τη δούμε σε ένα κατάλληλο παράδειγμα. Έστω αυτό το αυτόματο:

Πρόκειται για ένα μη ντετερμινιστικό πεπερασμένο αυτόματο, που αποδέχεται κάποια γλώσσα. Προς το παρόν δεν μας ενδιαφέρει ποια. Θα δούμε πώς μπορεί να γίνει ο υπολογισμός ενός τέτοιου αυτομάτου για τη λέξη εισόδου 11001. Η ιδέα είναι να επεξεργαζόμαστε ένα σύμβολο της λέξης και να βλέπουμε σε ποιες καταστάσεις μπορούμε να πάμε χάρη στις πολλαπλές μεταβάσεις για το ίδιο σύμβολο. Θυμόμαστε όλες αυτές τις καταστάσεις και στο επόμενο βήμα υποθέτουμε ότι βρισκόμαστε «σε όλες αυτές τις καταστάσεις ταυτόχρονα» και μας ενδιαφέρει πού μπορούμε να πάμε από εκεί.

Θα θυμόμαστε λοιπόν το σύνολο των καταστάσεων στις οποίες μπορεί να βρισκόμαστε και το αδιάβαστο μέρος της λέξης. Στην αρχή έχουμε το ζεύγος ⟨{q₀}, 11001⟩. Ξεκινάμε από την κατάσταση q₀ (αρχική κατάσταση) και η λέξη εισόδου είναι η 11001. Το αυτόματο φαίνεται ως εξής, με κόκκινο χρώμα και έντονα είναι σημειωμένη η κατάσταση στην οποία βρισκόμαστε:

Το πρώτο σύμβολο είναι το 1. Από την κατάσταση q₀ υπάρχει μόνο μία μετάβαση για το σύμβολο 1, οπότε πηγαίνουμε στην κατάσταση q₁. Θυμόμαστε το ζεύγος ⟨{q₁}, 1001⟩. Το αυτόματο φαίνεται ως εξής:

Συνεχίζουμε. Το αδιάβαστο μέρος της λέξης είναι το 1001, οπότε ψάχνουμε πάλι μεταβάσεις για το 1. Τώρα είναι δύο – πίσω στην κατάσταση q₀ και στην κατάσταση q₃. Εμείς πηγαίνουμε και στις δύο καταστάσεις ταυτόχρονα. Θυμόμαστε λοιπόν το ζεύγος ⟨{q₀, q₃}, 001⟩.

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

Σε αυτό το βήμα όμως δεν έχουμε τελειώσει ακόμη. Βλέπουμε ότι από την κατάσταση q₂ οδηγεί ε-μετάβαση στην κατάσταση q₄. Ξέρουμε ότι μια ε-μετάβαση μπορούμε να την κάνουμε «οποιαδήποτε στιγμή», χωρίς να διαβάσουμε επόμενο σύμβολο. Με άλλα λόγια – χωρίς να διαβάσουμε επόμενο σύμβολο της λέξης εισόδου, μπορούμε ακόμη να μετακινηθούμε στην κατάσταση q₄. Προσθέτουμε λοιπόν την κατάσταση q₄ στις καταστάσεις στις οποίες μπορεί να βρισκόμαστε: ⟨{q₁, q₂, q₄}, 01⟩. Το αυτόματο θα το χρωματίζαμε ως εξής:

Στη συνέχεια η είσοδος είναι το 0. Κοιτάμε πού μπορούμε να μετακινηθούμε από τις τρεις καταστάσεις στις οποίες βρισκόμαστε. Από την q₁ δεν μπορούμε να πάμε πουθενά, γιατί λείπει η μετάβαση για το 0. Ο υπολογισμός σε αυτόν τον κλάδο τελειώνει. Από την κατάσταση q₄ επίσης δεν πάμε πουθενά. Από την κατάσταση q₂ πηγαίνουμε πάλι στην κατάσταση q₂. Επειδή όμως από την q₂ οδηγεί ε-μετάβαση στην q₄, μπορούμε να φτάσουμε και στην q₄. Από το σύνολο καταστάσεων {q₁, q₂, q₄} μπορούμε λοιπόν για το σύμβολο 0 να φτάσουμε στο σύνολο καταστάσεων {q₂, q₄} και παίρνουμε το ζεύγος ⟨{q₂, q₄}, 1⟩:

Τέλος, στην είσοδο έχουμε το σύμβολο 1. Από την κατάσταση q₂ δεν πάμε πουθενά, ο υπολογισμός σε αυτόν τον κλάδο τελειώνει. Από την κατάσταση q₄ όμως πηγαίνουμε στις καταστάσεις q₃ και q₅. Παίρνουμε το ζεύγος ⟨{q₃, q₅}, ε⟩:

Το αυτόματο διάβασε πλέον ολόκληρη τη λέξη και «βρίσκεται» σε δύο καταστάσεις: q₃, q₅. Επειδή τουλάχιστον μία από αυτές είναι τελική κατάσταση, το αυτόματο αποδέχεται τη λέξη 11001.

Ο αλγόριθμος

Πρώτα χρειαζόμαστε μια συνάρτηση που παίρνει ως όρισμα ένα σύνολο καταστάσεων και υπολογίζει σε ποιες καταστάσεις μπορούμε ακόμη να φτάσουμε με ε-μεταβάσεις. Είσοδος είναι λοιπόν ένα αυτόματο ⟨Q, Σ, δ, q₀, F⟩ και ένα σύνολο καταστάσεων States, και έξοδος είναι ένα υπερσύνολο αυτών των καταστάσεων, στις οποίες μπορούμε να φτάσουμε με ε-μεταβάσεις. Αυτή την πράξη θα την ονομάζουμε ε-κλειστότητα του συνόλου States.

$\begin{aligned} Function E p s i l o n C l o s u r e (⟨ Q, Σ, δ, q_{0}, F ⟩, S t a t e s) \\ N e x t S t a t e s \leftarrow \emptyset \\ ForEach q \in S t a t e s Do \\ N e x t S t a t e s \leftarrow N e x t S t a t e s \cup {q} \cup δ (q, ε) \\ EndFor \\ If N e x t S t a t e s ∖ S t a t e s = \emptyset Do \\ Return S t a t e s \\ Else \\ Return E p s i l o n C l o s u r e (⟨ Q, Σ, δ, q_{0}, F ⟩, N e x t S t a t e s) \\ EndIf \\ EndFunction \end{aligned}$

Αυτή τη συνάρτηση τη χρησιμοποιούμε στη συνάρτηση που θα προσομοιώνει τη λειτουργία του μη ντετερμινιστικού αυτομάτου. Είσοδος είναι το αυτόματο, η λέξη εισόδου w = w₁w₂… w_n και το σύνολο καταστάσεων στις οποίες βρίσκεται τώρα το αυτόματο. Έξοδος είναι η απάντηση Ναι ή Όχι, ανάλογα με το αν το αυτόματο αποδέχεται ή δεν αποδέχεται τη δεδομένη λέξη.

$\begin{aligned} Function C o m p u t e N F A (⟨ Q, Σ, δ, q_{0}, F ⟩, w, S t a t e s) \\ If w = ϵ Do \\ If S t a t e s \cap F \neq \emptyset Do \\ Return YES \\ Else \\ Return NO \\ EndIf \\ EndIf \\ N e x t S t a t e s \leftarrow \emptyset \\ ForEach q \in S t a t e s Do \\ N e x t S t a t e s \leftarrow N e x t S t a t e s \cup δ (q, w_{1}) \\ EndFor \\ N e x t S t a t e s \leftarrow E p s i l o n C l o s u r e (⟨ Q, Σ, δ, q_{0}, F ⟩, N e x t S t a t e s) \\ Return C o m p u t e N F A (⟨ Q, Σ, δ, q_{0}, F ⟩, w_{2} w_{3} \dots w_{n}, N e x t S t a t e s) \\ EndFunction \end{aligned}$

Αν θέλουμε να ελέγξουμε αν το αυτόματο αποδέχεται τη λέξη w, καλούμε τη συνάρτηση ως εξής: ComputeNFA(⟨Q, Σ, δ, q₀, F⟩, w, EpsilonClosure(⟨Q, Σ, δ, q₀, F⟩, {q₀})).

Πηγές

Κεφάλαια: Πεπερασμένο αυτόματο, Πλήρες αυτόματο, Μη ντετερμινιστικό πεπερασμένο αυτόματο, Προσομοίωση NFA, Μετατροπή NFA σε DFA

« Προηγούμενο: Μη ντετερμινιστικό πεπερασμένο αυτόματο

Επόμενο: Μετατροπή NFA σε DFA »