Μη ντεντερμινιστικό πεπερασμένο αυτόματο (ΜΝΠΑ)
Σε αντίθεση με τα ΝΠΑ, σε ένα ΜΝΠΑ (Non Deterministic Finite Automaton) η κατάσταση μετάβασης δεν είναι καθορισμένη και επομένως για κάθε πιθανή είσοδο η μετάβαση από μια κατάσταση μπορεί να είναι σε οποιαδήποτε κατάσταση.
Και το ΜΝΠΑ είναι πεπερασμένο αφού έχει πεπερασμένο αριθμό καταστάσεων.
Τυπικός ορισμός
Ένα μη ντεντερμινιστικό πεπερασμένο αυτόματο ορίζεται ως μία πεντάδα M = (K, Σ, s, F, Δ) όπου:
- K (ή Q) είναι ένα πεπερασμένο σύνολο καταστάσεων
- Σ είναι ένα αλφάβητο
- s (q0) ∈ K είναι η αρχική κατάσταση
- F ⊆ K είναι το σύνολο των τελικών καταστάσεων και
- ∆ : είναι μία σχέση (όχι συνάρτηση) μετάβασης, δηλ. είναι ένα υποσύνολο του
Κ x (Σ ∪ {ε}) x Κ(όπου ε η κενή συμβολοσειρά)
Ισχύει:
Σε = Σ ∪ {ε}
Εναλλακτικά το δ μπορεί να οριστεί ως το σύνολο των μεταβάσεων από μία κατάσταση.
δ: KxΣ -> 2K
Έτσι, για ένα αυτόματο με:
K = {q0, q1}
Σ = {0, 1}
F = {q1}
Οι πιθανές (4) μεταβάσεις από το q0 με είσοδο έστω 0, δηλαδή δ(q0, 0) είναι:
q0, q1, {q0, q1}, και δ(q0, ε)
Όπου δ(q0, ε) μια τυχαία μετάβαση.
Κανόνες για ΜΝΠΑ
Ισχύουν οι παρακάτω γενικοί κανόνες
- Η μετάβαση από μια κατάσταση Χ σε μια επόμενη ΔΕΝ είναι πάντα καθορισμένη
- Μπορεί να υπάρχουν περισσότερες από μία επόμενες καταστάσεις (για δεδομένη είσοδο)
- Η μετάβαση μπορεί να είναι τυχαία ή αυθαίρετη (ε)
- Η είσοδος σε μια κατάσταση είναι ένα στοιχείο του αλφάβητου Σ ή το ε (empty string)
- Σε ένα ΝΠΑ η μετάβαση από μια κατάσταση μπορεί να είναι στο κενό (∅)
Για το αυτόματο
K = {a, b, c}
Σ = {0, 1}
s = a
F = {c}
Έστω ο παρακάτω πίνακας καταστάσεων/μεταβάσεων
| τρέχουσα κατάσταση | επόμενη κατάσταση για είσοδο 0 | επόμενη κατάσταση για είσοδο 1 |
|---|---|---|
| a | {a, b} | b |
| b | c | {a, c} |
| c | {b, c} | c |
Το αντίστοιχο διάγραμμα είναι:
Για το παρακάτω αυτόματο να σχεδιαστούν όλες οι πιθανές μεταβάσεις δ(q0, 1).
K = {q0, q1, q2}
Σ = {0, 1, 2}
F = {q2}
Ισχύουν τα παρακάτω:
- Η σχέση μετάβασης -σε αντίθεση με τη συνάρτηση των ντεντερμινιστικών ΠΑ- ορίζει για την τρέχουσα κατάσταση και συμβόλο εισόδου ένα σύνολο πιθανών επόμενων καταστάσεων
- Ο μη ντεντερμινισμός επιτρέπει τη μετάβαση σε επόμενη κατάσταση με τρόπο που προσδιορίζεται μόνο μερικώς από την τρέχουσα κατάσταση και το σύμβολο εισόδου
- Δεν καθορίζεται από τη μηχανή η επιλογή της νέας κατάστασης από το σύνολο όλων των πιθανών επόμενων καταστάσεων μετά από μετάβαση
- Θεωρούμε ότι ένα ΜΝΠΑ μπορεί σε μία χρονική στιγμή να βρίσκεται σε πολλές καταστάσεις
- Οι μη ντετερμινιστικές μηχανές
- δεν περιγράφουν υπολογισμούς που μπορεί να εκτελέσει ο Η/Υ
- είναι μηχανές που διευκολύνουν την περιγραφή/κατασκευή ντεντερμινιστικών ΠΑ
- Κάθε τριάδα (q, u, p) ∈ ∆ με u ∈ Σ ∪ {ε} και p, q ∈ K ονομάζεται μετάβαση του Μ.
- ε-μετάβαση: μετάβαση της μορφής (q, ε, p) που μπορεί να γίνει χωρίς να διαβαστεί σύμβολο εισόδου.
- Αν το Μ είναι στην κατάσταση q και το επόμενο σύμβολο εισόδου είναι το a ∈ Σ, τότε το Μ μπορεί να εκτελέσει
- τη μετάβαση (q, a, p)
- ή εφόσον αυτή ορίζεται, τη μετάβαση (q, ε, p)
- Μία συνολική κατάσταση του Μ είναι ένα στοιχείο του Κ×Σ*, όπως και στα ντεντερμινιστικά ΠΑ
Διαφορές ανάμεσα σε ΝΠΑ και ΜΝΠΑ
| ΝΠΑ | ΜΝΠΑ |
|---|---|
| Η μετάβαση σε επόμενη κατάσταση για συγκεκριμένη είσοδο είναι καθορισμένη | Η μετάβαση σε επόμενη κατάσταση για συγκεκριμένη είσοδο ΔΕΝ είναι καθορισμένη |
| Υπάρχει μόνο μία επόμενη κατάσταση | Μπορεί να υπάρχουν περισσότερες από μία επόμενες καταστάσεις |
| Αντιστοιχεί μόνο μία κατάσταση σε κάθε χρονική στιγμή | Μπορεί να αντιστοιχεί σε πολλές καταστάσεις ταυτόχρονα (πάραλληλες διαδρομές) |
| Κάθε μετάβαση αντιστοιχεί σε συγκεκριμένη είσοδο | Μπορεί να έχουμε μετάβαση με κενή (ε) είσοδο |
| Δεν επιτρέπεται κενή συμβολοσειρά | Επιτρέπεται κενή συμβολοσειρά |
| Το Backtracking είναι δυνατό | Το Backtracking δεν είναι πάντα δυνατό |
| Μια συμβολοσειρά είναι δεκτή όταν καταλήγει σε τελική κατάσταση | Μια συμβολοσειρά είναι δεκτή όταν τουλάχιστον μία από όλες τις πιθανές μεταβάσεις καταλήγει σε τελική κατάσταση |
Τις παραπάνω διαφορές μπορούμε να τις διακρίνουμε και στο παρακάτω διάγραμμα.
Αριστερά ένα αυτόματο και δεξιά ένα μη αυτόματο με τις διαφορές που έχει σε σχέση με το αυτόματο.
Έστω το ΜΝΠΑ με Σ = {0, 1}
Σύμφωνα με το διάγραμμα το ΠΑ είναι ΜΝΠΑ διότι:
- Υπάρχουν δύο ακμές με είσοδο 1 από την κατάσταση q1
- Δεν υπάρχουν μεταβάσεις από την κατάσταση q4
- Η μετάβαση από την κατάσταση q2 μπορεί να εκτελεστεί χωρίς είσοδο (ε)
Επίσης ο αντίστοιχος πίνακας καταστάσεων-μεταβάσεων είναι:
Να σχεδιαστεί αυτόματο που να δέχεται συμβολοσειρές που τελειώνουν σε 0 με:
K = {q0, q1}
Σ = {0, 1}
s = q0
F = {q1}
Το διάγραμμα είναι:
Στο παραπάνω παράδειγμα να ελεγχθεί αν η συμβολοσειρά 100 είναι αποδεκτή.
Λύση: Μπορούμε να σχεδιάσουμε σε ένα διάγραμμα τις πιθανές διαδρομές και να ελέγξουμε αν κάποια από αυτές καταλήγει σε τελική μετάβαση όπως παρακάτω.
Στο παραπάνω παράδειγμα να ελεγχθεί αν η συμβολοσειρά 001 είναι αποδεκτή.
Στο παραπάνω παράδειγμα μπορείτε να διακρίνετε το πρότυπο (pattern) συμβολοσειρών που δέχεται το μη αυτόματο.
Να σχεδιαστεί μη αυτόματο που να δέχεται συμβολοσειρές που αρχίζουν από 0.
Να συγκριθεί με το αντίστοιχο αυτόματο.
Να σχεδιαστεί μη αυτόματο που να δέχεται συμβολοσειρές που έχουν μήκος 2.
Να συγκριθεί με το αντίστοιχο αυτόματο.
Γλώσσα ΜΝΠΑ
Η γλώσσα που γίνεται δεκτή από ένα ΜΝΠΑ Μ, συμβολίζεται με L(M) και περιλαμβάνει όλες τις συμβολοσειρές που δέχεται το Μ.