Μετατροπή ΜΝΠΑ σε ΝΠΑ (ndfa to dfa)
Μπορούμε να μετατρέψουμε ένα ΜΝΠΑ σε ένα ισοδύναμο ΝΠΑ.
Για να είναι ένα ΝΠΑ ισοδύναμο ενός ΜΝΠΑ πρέπει να ισχύει:
L(Y) = L(X)
Όπου Χ ένα ΜΝΠΑ και Υ ένα ΝΠΑ
Θα πρέπει δηλαδή οι συμβολοσειρές που είναι αποδεκτές από το ΜΝΠΑ να είναι και από το ΝΠΑ.
Το αλφάβητο Σ και η αρχική κατάσταση πρέπει να είναι ίδια και στα δύο αυτόματα.
Αλγόριθμος μετατροπής
Στη συνέχεια θα δούμε τα βήματα για να μετατρέψουμε ένα ΜΝΠΑ σε ΝΠΑ και θα χρησιμοποιήσουμε το παρακάτω διάγραμμα.
1. Δημιουργία πίνακα μεταβάσεων του ΜΝΠΑ
| q | δ(q, 0) | δ(q, 1) |
|---|---|---|
| a | {a,b,c,d,e} | {d,e} |
| b | {c} | {e} |
| c | {∅} | {b} |
| d | {e} | {∅} |
| e | {∅} | {∅} |
2. Δημιουργία πίνακα μεταβάσεων του ΝΠΑ
Ξεκινάμε από την αρχική κατάσταση και δημιουργούμε νέες σύνθετες καταστάσεις σύμφωνα με τις εισόδους (0,1) στην κάθε κατάσταση.
Κάθε φορά που δημιουργείται μια νέα κατάσταση ελέγχουμε τις εισόδους αυτής.
Εάν μέσα σε μια σύνθετη κατάσταση υπάρχει τελική κατάσταση, τότε και η σύνθετη χαρακτηρίζεται τελική.
Αυτό επαναλαμβάνεται μέχρι να φτάσουμε σε ένα τέλος.
| q | δ(q, 0) | δ(q, 1) |
|---|---|---|
| [a] | [a,b,c,d,e] | [d,e] |
| [a,b,c,d,e] | [a,b,c,d,e] | [b,d,e] |
| [d,e] | [e] | ∅ |
| [b,d,e] | [c,e] | [e] |
| [e] | ∅ | ∅ |
| [c,e] | ∅ | [b] |
| [b] | [c] | [e] |
| [c] | ∅ | [b] |
3. Δημιουργία διαγράμματος ΝΠΑ
Για τα κενά (∅) πρέπει να δημιουργηθούν παγίδες (traps) ή έστω μία.
Να δημιουργηθεί μη αυτόματο για λέξεις που αρχίζουν από 0. Στη συνέχεια να σχεδιαστεί το ισοδύναμο αυτόματο.
Το διάγραμμα είναι:
Ο πίνακας καταστάσεων μεταβάσεων για το μη αυτόματο είναι:
| q | δ(q, 0) | δ(q, 1) |
|---|---|---|
| Α | Β | ∅ |
| Β | Β | Β |
Ο πίνακας καταστάσεων μεταβάσεων για το αυτόματο είναι:
| q | δ(q, 0) | δ(q, 1) |
|---|---|---|
| A | B | C |
| C | C | C |
| B | B | B |
Το διάγραμμα είναι:
Να δημιουργηθεί μη αυτόματο για λέξεις που λήγουν σε 1. Στη συνέχεια να σχεδιαστεί το ισοδύναμο αυτόματο.
Το διάγραμμα είναι:
Ο πίνακας καταστάσεων μεταβάσεων για το μη αυτόματο είναι:
| q | δ(q, 0) | δ(q, 1) |
|---|---|---|
| Α | A | {A, B} |
| Β | ∅ | ∅ |
Ο πίνακας καταστάσεων μεταβάσεων για το αυτόματο είναι:
| q | δ(q, 0) | δ(q, 1) |
|---|---|---|
| A | A | AB |
| AB | A | AB |
Το διάγραμμα είναι:
Να δημιουργηθεί μη αυτόματο για λέξεις που λήγουν σε 01. Στη συνέχεια να σχεδιαστεί το ισοδύναμο αυτόματο.
Το διάγραμμα είναι:
Ο πίνακας καταστάσεων μεταβάσεων για το μη αυτόματο είναι:
| q | δ(q, 0) | δ(q, 1) |
|---|---|---|
| Α | {A, B} | A |
| Β | ∅ | C |
| C | ∅ | ∅ |
Ο πίνακας καταστάσεων μεταβάσεων για το αυτόματο είναι:
| q | δ(q, 0) | δ(q, 1) |
|---|---|---|
| A | AB | A |
| AB | AB | AC |
| AC | AB | A |
Το διάγραμμα είναι:
Να δημιουργηθεί μη αυτόματο για λέξεις με προτελευταίο σύμβολο το 1. Στη συνέχεια να σχεδιαστεί το ισοδύναμο αυτόματο.
Το διάγραμμα είναι:
Ο πίνακας καταστάσεων μεταβάσεων για το μη αυτόματο είναι:
| q | δ(q, 0) | δ(q, 1) |
|---|---|---|
| Α | Α | {A, B} |
| Β | C | C |
| C | ∅ | ∅ |
Ο πίνακας καταστάσεων μεταβάσεων για το αυτόματο είναι:
| q | δ(q, 0) | δ(q, 1) |
|---|---|---|
| A | A | AB |
| AB | AC | ABC |
| AC | A | AB |
| ABC | AC | ABC |
Το διάγραμμα είναι:
Να μετατραπεί το παρακάτω ΜΝΠΑ σε ΝΠΑ.
Αρχικά ο πίνακας καταστάσεων μεταβάσεων είναι:
| q | δ(q, 0) | δ(q, 1) |
|---|---|---|
| a | a | b |
| b | {b,c} | b |
| c | c | {b,c} |
Δημιουργούμε τον πίνακα καταστάσεων μεταβάσεων για το ΝΠΑ.
| q | δ(q, 0) | δ(q, 1) |
|---|---|---|
| [a] | [a] | [b] |
| [b] | [b,c] | [b] |
| [b,c] | [b,c] | [b,c] |
Και το αντίστοιχο διάγραμμα είναι.
Να μετατραπεί το παρακάτω ΜΝΠΑ (με εισόδους ε) σε ΝΠΑ.
Για μετατροπή ΜΝΠΑ (με εισόδους ε) πρέπει πρώτα να εξαλείψουμε το ε.
Αυτό γίνεται ως εξής:
Με το σκεπτικό ότι για κάποια χρονική στιγμή μπορεί να βρισκόμαστε σε μία από τις τρεις καταστάσεις [a, b, c] έχουμε:
| q | δ(q, 0) | δ(q, 1) |
|---|---|---|
| [a,b,c] | [d] | [d] |
| [d] | ∅ | [e] |
Το τελικό διάγραμμα είναι:
Εργαστήριο
Να μετατραπεί το παρακάτω ΜΝΠΑ σε ΝΠΑ.
Να μετατραπεί το παρακάτω ΜΝΠΑ (με εισόδους ε) σε ΝΠΑ.
Υπόδειξη: Διακρίνουμε περιπτώσεις για a, b, c.