Mealy και Moore Μηχανές
Οι παρακάτω δύο μηχανές (με πεπερασμένες καταστάσεις) παράγουν έξοδο (output) σε μια είσοδο (input) σε αντίθεση με τα προηγούμενα που παρήγαγαν μόνο αποδοχή ή όχι της εισόδου.
Mealy Machine
Η μηχανή Machine είναι ένα αυτόματο πεπερασμένων καταστάσεων (FSM) της οποίας η έξοδος εξαρτάται από την τρέχουσα κατάσταση αλλά και από την τρέχουσα είσοδο.
Βρίσκει εφαρμογή σε τεχνολογίες όπως κρυπτογραφία, ανάγνωση bar code κλπ.
Ορισμός
Περιγράφεται από μια πλειάδα (tuple) έξι (6) στοιχείων.
Κ Καταστάσεις. Σύνολο πεπερασμένου αριθμού καταστάσεων (συμβολίζεται και με Q) Σ Αλφάβητο εισόδου. Σύνολο πεπερασμένου αριθμού συμβόλων Δ Αλφάβητο εξόδου. Σύνολο πεπερασμένου αριθμού συμβόλων (συμβολίζεται και με Ο) δ Συνάρτηση μετάβασης εισόδου (δ: K x Σ → K) λ Συνάρτηση εξόδου (λ: K × Σ → Δ) q0 Αρχική κατάσταση (q0 ∈ K)
Οι δύο παραπάνω συναρτήσεις μπορούν να συμπτυχθούν σε μία: Τ: K x Σ → K x Δ
Για κάθε κατάσταση και κάθε είσοδο επιτρέπεται μόνο μία μετάβαση.
Σημειώστε ότι η μηχανή Mealy δεν έχει τελικές καταστάσεις.
Ακολουθεί διάγραμμα μιας μηχανής Mealy
Και ο πίνακας μεταβάσεων/εξόδων είναι:
q 0->state/output 1->state/output --------------------------------------- A B/a A/b B A/b B/a
Για την παραπάνω μηχανή, μια είσοδος έστω: 1010
έχει ώς έξοδο: baab
.
Αυτό μπορούμε να το διαπιστώσουμε και με το παρακάτω διάγραμμα.
Θεωρούμε Σ = {0, 1}
και Δ = {a, b}
.
Για το παρακάτω παράδειγμα θα χρειαστούμε τον παρακάτω ορισμό:
Το συμπλήρωμα ως προς ένα ενός αριθμού αποτελεί ο αριθμός ο οποίος προκύπτει αν αντιστρέψουμε κάθε bit του αρχικού αριθμού. Για παράδειγμα το συμπλήρωμα ως προς ένα του αριθμού 10100
είναι ο αριθμός 01011
.
Και το ζητούμενο είναι να κατασκευαστεί μηχανή Mealy η οποία θα έχει ως έξοδο το συμπλήρωμα ως προς ένα ενός αριθμού.
Να κατασκευαστεί μηχανή η οποία για είσοδο 1
όπου προηγείται το 0
(δηλαδή έχει τη μορφή 01
) να έχει έξοδο το a
.
Δηλαδή για είσοδο 01
η έξοδος θα είναι ba, για 0010 η έξοδος θα είναι bbab κλπ..
Το διάγραμμα είναι:
Για επαλήθευση θα δοκιμάσουμε την είσοδο 01101
. Το αποτέλεσμα είναι:
0 -> b 1 -> a 1 -> b 0 -> b 1 -> a
Να κατασκευαστεί μηχανή που θα δέχεται συμβολοσειρές που λήγουν σε aa
.
Θεωρούμε Σ = {a, b}
και Δ = {0, 1}
.
Για να λήγει σε aa
θα πρέπει στο δεύτερο a
η εξοδος να είναι 1
.
Το αρχικό διάγραμμα χωρίς εξόδους είναι:
Από το παραπάνω διάγραμμα παρατηρούμε ότι μόνο με έξοδο 1
στην κατάσταση Β
έχουμε συμβολοσειρά που λήγει σε aa
.
Άρα το τελικό διάγραμμα (με εξόδους) είναι:
Να κατασκευαστεί μηχανή που θα δέχεται συμβολοσειρές που λήγουν σε aa
ή bb
.
Θεωρούμε Σ = {a, b}
και Δ = {0, 1}
.
Για να λήγει σε aa
ή bb
θα πρέπει στο δεύτερο a
ή b
η εξοδος να είναι 1
.
Να κατασκευαστεί μηχανή Mealy έτσι ώστε αν υπάρχει στην είσοδο υπο-συμβολοσειρά 101 να δίνει έξοδο a (στο 101), αν υπάρχει 110 να δίνει b (στο 110) και σε διαφορετική περίπτωση c.
Θεωρούμε Σ = {0, 1}
και Δ = {a, b, c}
.
Να κατασκευαστεί μηχανή Mealy έτσι ώστε αν στην είσοδο η συμβολοσειρά τελειώνει σε 00 να δίνει έξοδο a, αν τελειώνει σε 11 να δίνει b και σε διαφορετική περίπτωση c.
Θεωρούμε Σ = {0, 1}
και Δ = {a, b, c}
.
Moore Machine
Η μηχανή Moore είναι ένα αυτόματο πεπερασμένων καταστάσεων (FSM) της οποίας η έξοδος εξαρτάται από την τρέχουσα κατάσταση μόνο.
Ορισμός
Περιγράφεται από μια πλειάδα (tuple) έξι (6) στοιχείων.
Κ Καταστάσεις. Σύνολο πεπερασμένου αριθμού καταστάσεων (συμβολίζεται και με Q) Σ Αλφάβητο εισόδου. Σύνολο πεπερασμένου αριθμού συμβόλων Δ Αλφάβητο εξόδου. Σύνολο πεπερασμένου αριθμού συμβόλων (συμβολίζεται και με Ο) δ Συνάρτηση μετάβασης εισόδου (δ: K x Σ → K) λ Συνάρτηση εξόδου (λ: K → Δ) q0 Αρχική κατάσταση (q0 ∈ K)
Στη μηχανή Moore έχουμε έξοδο στην αρχική κατάσταση πριν ακόμα έχουμε είσοδο. Αυτό έχει σαν συνέπεια η έξοδος να έχει ένα παραπάνω σύμβολο από την είσοδο.
Σημειώστε ότι η μηχανή Moore (όπως και η Mealy) δεν έχει τελικές καταστάσεις.
Ακολουθεί διάγραμμα μιας μηχανής Moore
Θεωρούμε Σ = {0, 1}
και Δ = {a, b}
.
Και ο πίνακας καταστάσεων/εξόδων είναι:
q 0->state/output 1->state/output --------------------------------------- A/a A B/b A/a B B/b A/a
Για την παραπάνω μηχανή, μια είσοδος έστω: 1010
έχει ώς έξοδο: aabab
.
Παρατηρήστε ότι η έξοδος ξεκινάει με a
χωρίς αρχική είσοδο γι' αυτό έχει ένα σύμβολο παραπάνω.
Να κατασκευαστεί μηχανή η οποία για μια είσοδο που περιέχει τη σειρά 01
να έχει έξοδο το a
.
Δηλαδή για 01
η έξοδος θα είναι .ba
, για 0010
η έξοδος θα είναι .bbab
κλπ.
Το διάγραμμα είναι:
Για επαλήθευση θα δοκιμάσουμε την είσοδο 01101
. Το αποτέλεσμα είναι:
0 -> b 1 -> a 1 -> b 0 -> b 1 -> a
Να κατασκευαστεί μηχανή που θα δέχεται συμβολοσειρές που λήγουν σε aa
.
Θεωρούμε Σ = {a, b}
και Δ = {0, 1}
.
Μπορούμε να θεωρήσουμε ότι σε δύο διαδοχικά a
θα έχω έξοδο 1. Άρα για να λήγει η συμβολοσειρά σε aa
θα πρέπει να τελευταίο ψηφίο να είναι 1
.
Το διάγραμμα είναι:
Για επαλήθευση θα δοκιμάσουμε την είσοδο baabaa
. Το αποτέλεσμα είναι:
0001001
Να κατασκευαστεί μηχανή που θα μετράει τις φορές της σειράς abb
σε μια συμβολοσειρά.
Θεωρούμε Σ = {a, b}
και Δ = {0, 1}
.
Μπορούμε να θεωρήσουμε ότι για κάθε σειρά abb
θα έχω έξοδο 1
.
Το διάγραμμα είναι:
Για επαλήθευση θα δοκιμάσουμε την είσοδο abbabb
. Το αποτέλεσμα είναι:
0001001
Από το αποτέλεσμα μπορούμε να μετρήσουμε τις φορές του 1
που εδώ είναι ίσον με 2.
Να κατασκευαστεί μηχανή Moore που να δίνει στη έξοδο 1 για συμβολοσειρές με μονό αριθμό 1, και 0 για συμβολοσειρές με ζυγό αριθμό 1.
Θεωρούμε Σ = {0, 1}
και Δ = {0, 1}
.
Να κατασκευαστεί μηχανή Moore που να δίνει στο τέλος της έξοδου y για συμβολοσειρές που περιέχουν 1010, και n σε διαφορετική περίπτωση.
Θεωρούμε Σ = {0, 1}
και Δ = {y, n}
.