Μη ντετερμινιστικό πεπερασμένο αυτόματο

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

Παράδειγμα

Δες το επόμενο διάγραμμα αυτομάτου:

Τι το παράξενο έχει; Ότι από τον κόμβο q₀ οδηγούν δύο ακμές για το σύμβολο 0. Αν λοιπόν προσπαθήσουμε να αποδεχτούμε τη λέξη 001, φαίνεται ότι το αυτόματο δεν θα ξέρει αν πρέπει να μείνει στην κατάσταση q₀ ή αν πρέπει να ακολουθήσει τη μετάβαση προς την q₁. Ένα τέτοιο αυτόματο θα ήταν μη ντετερμινιστικό.

Ντετερμινισμός με αυτή την έννοια σημαίνει ότι σε κάθε περίπτωση είναι σαφές τι θα κάνει το αυτόματο, δεν υπάρχει περιθώριο για ασάφεια. Το ντετερμινιστικό αυτόματο έχει για κάθε κατάσταση και κάθε σύμβολο μόνο μία μετάβαση. Ο μη ντετερμινισμός σημαίνει ασάφεια – από μια κατάσταση μπορεί να οδηγούν, ας πούμε, τρεις μεταβάσεις για το ίδιο σύμβολο.

Και πώς αποφασίζει λοιπόν το αυτόματο; Το μη ντετερμινιστικό αυτόματο επιλέγει πάντα (μερικές φορές λέμε και «μαντεύει») τη μετάβαση που οδηγεί στο να αποδεχτεί τη λέξη, αν αυτό είναι δυνατό.

Αν βάλουμε στο αυτόματο τη λέξη 001, το αυτόματο έχει αυτές τις δυνατότητες να χειριστεί τη λέξη:

$\begin{array}{r} q_{0} \to q_{0} \to q_{0} \to q_{0} \\ q_{0} \to q_{0} \to q_{1} \to q_{2} \end{array}$

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

Πώς καταφέρνει να επιλέξει αυτόματα τον «ευνοϊκό» κλάδο; Μπορούμε να το φανταστούμε έτσι: το μη ντετερμινιστικό αυτόματο διατρέχει όλους τους δυνατούς κλάδους και αν βρει κλάδο στον οποίο αποδέχεται τη λέξη, τότε αποδέχεται τη λέξη. Πώς θα μπορούσε να διατρέξει όλους τους κλάδους; Απλούστατα, τη στιγμή που βρίσκεται σε κατάσταση από την οποία για το τρέχον σύμβολο οδηγούν n ακμές, το αυτόματο αντιγράφει τον εαυτό του n φορές και κάθε αντίγραφο ακολουθεί διαφορετική διαδρομή. Έτσι διατρέχουμε σταδιακά όλες τις δυνατότητες.

Αναπαράσταση του υπολογισμού του αυτομάτου με δέντρο

Τροποποιούμε ελαφρά το προηγούμενο αυτόματο:

Ο μη ντετερμινισμός παραμένει στην πρώτη κατάσταση. Το προηγούμενο αυτόματο αποδεχόταν όλες τις λέξεις που τελειώνουν σε 01. Αυτό το τροποποιημένο αυτόματο αποδέχεται όλες τις λέξεις που περιέχουν την υπολέξη 01. Αποδέχεται λοιπόν για παράδειγμα τη λέξη 101 ή 0101. Όλους τους κλάδους του υπολογισμού μπορούμε εύκολα να τους οπτικοποιήσουμε με δέντρο, π.χ. για τη λέξη 01010 το δέντρο θα μπορούσε να μοιάζει ως εξής:

Στην αρχή βρισκόμαστε στην αρχική κατάσταση q₀. Στην είσοδο έχουμε τη λέξη 01010, ο πρώτος χαρακτήρας που δεν έχει διαβαστεί είναι το 0. Από την κατάσταση q₀ οδηγούν δύο μεταβάσεις για το σύμβολο 0, προς τις καταστάσεις q₀ και q₁. Το δέντρο θα έχει έτσι σε αυτόν τον κόμβο δύο παιδιά: q₀ και q₁. Στη συνέχεια διαβάζουμε το σύμβολο 1. Εκεί δεν υπάρχει καμία ασάφεια, μετακινούμαστε στις καταστάσεις q₀ και q₂. Στη συνέχεια διαβάζουμε τον χαρακτήρα 0, στον αριστερό κλάδο ξανά προκύπτει ασάφεια, χωρίζουμε τον υπολογισμό σε δύο ακόμη κλάδους. Στον έναν ξανά μένουμε στην q₀ και στον άλλον πηγαίνουμε στην q₁. Και ούτω καθεξής.

Πρόσεξε ότι συνολικά δύο κλάδοι τελειώνουν στην κατάσταση q₂, σε τελική κατάσταση. Υπάρχουν δύο κλάδοι του υπολογισμού με τους οποίους το αυτόματο μπορεί να αποδεχτεί τη δοσμένη λέξη. Αυτό το αυτόματο θα αποδεχόταν έτσι τη λέξη 01010. Μπορούμε να δοκιμάσουμε να σχηματίσουμε παρόμοιο δέντρο για τη λέξη 1000.

Ο υπολογισμός είτε παραμένει στην κατάσταση q₀ είτε περνά στην κατάσταση q₁, αλλά από εκεί δεν έχει πού να πάει παρακάτω, επειδή στην είσοδο έχουν μείνει μόνο μηδενικά και η κατάσταση q₁ έχει μετάβαση μόνο για το σύμβολο 1. Κανένας κλάδος του υπολογισμού δεν τελειώνει σε τελική κατάσταση, άρα το αυτόματο δεν αποδέχεται τη λέξη 1000.

ε-μεταβάσεις

Στα μη ντετερμινιστικά αυτόματα μπορούμε επιπλέον να χρησιμοποιούμε ε-μεταβάσεις. Αυτές είναι μεταβάσεις που μπορούμε να εκτελέσουμε όποιο σύμβολο κι αν είναι στην είσοδο, και μάλιστα χωρίς να διαβάσουμε κάποιο σύμβολο της λέξης. Πώς θα μπορούσαμε να γράψουμε ένα μη ντετερμινιστικό αυτόματο που θα αποδεχόταν την κενή λέξη, όλες τις λέξεις που αποτελούνται μόνο από άσους και τις λέξεις της μορφής (10)ⁿ, δηλαδή 10, 1010, …;

Χωρίσαμε το αυτόματο σε δύο «υποαυτόματα». Το πάνω φροντίζει να αναγνωρίζει τις λέξεις που αποτελούνται από 1, το κάτω φροντίζει για τις λέξεις της μορφής (10)ⁿ. Θα δοκιμάσουμε να αποδεχτούμε τη λέξη 111. Το αυτόματο βρίσκεται στην αρχή στην κατάσταση q₀ και έχει στην είσοδο τη λέξη 111. Επειδή έχει στη διάθεσή του ε-μεταβάσεις, μπορεί να αποφασίσει να περάσει στην κατάσταση q₁ ή q₂, ανάλογα με το τι το βολεύει. Βλέπουμε ότι θα το βολέψει να περάσει στην κατάσταση q₁. Το αυτόματο πηγαίνει εκεί. Στην είσοδο έχει ακόμη τη λέξη 111! Μόλις τώρα αρχίζει να διαβάζει τα σύμβολα της λέξης και να περνά από την κατάσταση q₁ ξανά στην q₁, μέχρι να διαβάσει ολόκληρη τη λέξη και να την αποδεχτεί.

Αν δοκιμάζαμε να αποδεχτούμε τη λέξη 1010, το αυτόματο θα περνούσε στην αρχή στην κατάσταση q₂ και μόνο από εκεί θα άρχιζε να επεξεργάζεται τα σύμβολα και πάλι θα αποδεχόταν τη λέξη.

Για τη λέξη 1100 το αυτόματο θα μπορούσε να κάνει οτιδήποτε, δεν υπάρχει τρόπος να αποδεχτεί μια τέτοια λέξη.

Οι ε-μεταβάσεις και ο μη ντετερμινισμός μας διευκολύνουν σε πολλά τη δουλειά, για παράδειγμα η απόδειξη ότι η ένωση κανονικών γλωσσών είναι πάλι κανονική γλώσσα μπορεί να γραφτεί με ε-μεταβάσεις πολύ πιο απλά απ' ό,τι στην περίπτωση των ντετερμινιστικών πεπερασμένων αυτομάτων. Σε αυτή την απόδειξη είχαμε παραδείγματα τέτοιων αυτομάτων

και

και στη συνέχεια κατασκευάσαμε ένα πεπερασμένο ντετερμινιστικό αυτόματο που αποδεχόταν την ένωση των δύο γλωσσών. Με ε-μεταβάσεις μπορούμε να κατασκευάσουμε ένα τέτοιο αυτόματο ως εξής:

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

Ορισμός του μη ντετερμινιστικού αυτομάτου

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

Στην ντετερμινιστική εκδοχή η συνάρτηση για την κλήση δ(q, w) μπορούσε να επιστρέψει μόνο μία κατάσταση, ενώ στη μη ντετερμινιστική εκδοχή μπορεί να επιστρέψει περισσότερες καταστάσεις – αν για ένα σύμβολο είναι ορισμένες περισσότερες μεταβάσεις. Επειδή πρέπει να ορίσουμε και τις ε-μεταβάσεις, συμβολίζουμε το σύνολο Σ ∪ {ε} ως σύνολο Σ_ε, δηλαδή Σ_ε = Σ ∪ {ε}. Τη συνάρτηση δ την ορίζουμε λοιπόν ως

$δ : Q \times Σ_{ε} \to 2^{Q}$

Το 2^Q δηλώνει το δυναμοσύνολο, το σύνολο όλων των υποσυνόλων του συνόλου Q. Η τυποποίηση του υπολογισμού είναι πολύ παρόμοια με αυτήν των πεπερασμένων αυτομάτων. Η διαμόρφωση του αυτομάτου είναι πάλι ένα ζεύγος ⟨q, w⟩ ∈ Q × Σ^∗. Το βήμα υπολογισμού ↦ είναι μια σχέση στο σύνολο των διαμορφώσεων τέτοια ώστε

$⟨ q_{i}, w_{0} w_{1} \dots w_{n} ⟩ \mapsto ⟨ q_{j}, w_{1} \dots w_{n} ⟩,$

αν και μόνο αν q_j ∈ δ(q_i, w₀). Σε αυτή την πρόταση βρισκόταν η μεγαλύτερη διαφορά. Στα ντετερμινιστικά αυτόματα είχαμε γράψει αυτή τη συνθήκη ως q_j = δ(q_i, w₀), επειδή η συνάρτηση δ επέστρεφε πάντα μία κατάσταση. Η μη ντετερμινιστική εκδοχή της συνάρτησης μετάβασης επιστρέφει σύνολο καταστάσεων, γι' αυτό υπάρχει εκεί το σύμβολο ∈. Την ανακλαστική και μεταβατική κλειστότητα της σχέσης θα τη συμβολίζουμε πάλι ↦ ^∗. Λέμε ότι το αυτόματο αποδέχεται τη λέξη w αν και μόνο αν υπάρχει q_f ∈ F τέτοιο ώστε

$⟨ q_{0}, w ⟩ \mapsto^{*} ⟨ q_{f}, ε ⟩ .$

Πηγές

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

« Προηγούμενο: Πλήρες αυτόματο

Επόμενο: Προσομοίωση NFA »