Ισοδυναμία αυτόματων
Δύο αυτόματα μπορεί να είναι ισοδύναμα και παρακάτω περιγράφεται ο τρόπος με τον οποίο μπορούμε να το διαπιστώσουμε.
Προϋποθέσεις για ισοδυναμία
Πρέπει να ισχύουν τα παρακάτω:
- Για ένα ζευγάρι καταστάσεων έστω
{qi, qj}η μετάβαση για είσοδοa ∈ Σορίζεται ως{qa, qb}όπουδ(qi, a) = qaκαιδ(qj, a) = qb.
Εάν ταqaκαιqbανήκουν σε διαφορετικό τύπο καταστάσεων (τελική και μη τελική κατάσταση), τότε τα αυτόματα δεν είναι ισοδύναμα. - Εάν σε ένα αυτόματο η αρχική κατάσταση είναι και τελική τότε για να μπορεί να είναι ένα άλλα ισοδύναμο πρέπει να έχει επίσης την αρχική κατάσταση ως τελική.
Τα δύο παρακάτω αυτόματα είναι ισοδύναμα.
καταστάσεις είσοδος c είσοδος d ---------------------------------------- (A, D) (A, D) (B, E) (B, E) (C, F) (A, D) (C, F) (B, G) (C, F) (B, G) (C, F) (A, D)
- Αρχικά επιλέγουμε τις αρχικές καταστάσεις των δύο αυτόματων.
- Βρίσκουμε τις καταστάσεις για τις μεταβάσεις των αντίστοιχων εισόδων.
- Επαναλαμβάνουμε για κάθε νέο ζεύγος που προκύπτει σε κάθε νέα γραμμή.
- Σε κάθε γραμμή ελέγχουμε τα ζεύγη που προκύπτουν αν είναι του ίδιου τύπου.
- Αν βρεθεί ζεύγος με καταστάσεις διαφορετικού τύπου, τότε τα αυτόματα δεν είναι ισοδύναμα και εκεί τελειώνει η διαδικασία.
- Αν δεν προκύψει νέο ζεύγος στην όλη διαδιακασία και δεν έχει προκύψει περίπτωση μη ισοδυναμίας, εκεί τελειώνουμε την διαδικασία και θεωρούμε τα αυτόματα ισοδύναμα.
Να ελεγχθούν για ισοδυναμία τα παρακάτω αυτόματα.
