Πεπερασμένα αυτόματα και τρόποι ρύθμισης τους. Automata Τρόποι ρύθμισης Βασικοί ορισμοί n Πεπερασμένο. Τυπικές ή αυτόματες γλώσσες περιγραφής

Όπως αναφέρθηκε προηγουμένως, ο Υ (x,q)καθορίζει τη σειρά μετατροπής των συμβόλων εισόδου και την κατάσταση του αυτόματου στον προηγούμενο κύκλο στην κατάσταση του επόμενου, ένα Q (x,q) -μετατροπή των συμβόλων εισόδου και της κατάστασης του αυτόματου στον τρέχοντα κύκλο σε σύμβολο εξόδου. Αν ένα q 0 είναι η αρχική κατάσταση του αυτόματου και Εγώ- μετρήστε τον αριθμό και στη συνέχεια το έργο του περιγράφεται από το σύστημα:

Αυτές οι αναλογίες ονομάζονται συστήματα κανονικών εξισώσεωνπεπερασμένο αυτόματο. Μπορείτε να τα χρησιμοποιήσετε από q 0,βρείτε διαδοχικά όλες τις επόμενες καταστάσεις του αυτόματου και των συμβόλων εξόδου.

Υπάρχουν δύο τύποι μηχανών - αρχικόςκαι μη αρχικό. ΣΤΟΤα αρχικά αυτόματα έχουν μια σταθερή αρχική κατάσταση (δηλαδή ξεκινούν πάντα από την ίδια κατάσταση q0).Σε μη αρχικά αυτόματα, οποιοδήποτε από το σύνολο Q; αυτή η επιλογή καθορίζει την περαιτέρω συμπεριφορά του αυτόματου.

Η αναπαράσταση ενός συγκεκριμένου πεπερασμένου αυτόματου στην πραγματικότητα ανάγεται σε μια περιγραφή των συναρτήσεων του αυτόματου που το καθορίζουν. Από το σύστημα (9.3) προκύπτει ότι για έναν πεπερασμένο αριθμό πιθανών εσωτερικών καταστάσεων, ο αριθμός των πιθανών τιμών των αυτόματων συναρτήσεων αποδεικνύεται επίσης πεπερασμένος. Μπορούν να περιγραφούν με διάφορους τρόπους, ο πιο συνηθισμένος από τους οποίους είναι πινακοειδήςκαι με τη βοήθεια διαγράμματα.

ΣΤΟ πίνακαΟι αυτόματες συναρτήσεις δίνονται από δύο πεπερασμένους πίνακες, που ονομάζονται αντίστοιχα μήτρα μετάβασηςκαι μήτρα εξόδου.Σε αυτούς τους πίνακες, οι σειρές υποδηλώνονται με τα γράμματα του αλφαβήτου εισόδου και οι στήλες με τα γράμματα του εσωτερικού αλφαβήτου (σύμβολα που κωδικοποιούν την εσωτερική κατάσταση του αυτόματου). Στον πίνακα μετάβασης στη διασταύρωση της σειράς (xk)και στήλη (qr)τοποθετούνται οι τιμές της συνάρτησης Υ ( q r, x k),ένα στον πίνακα των εξόδων - οι τιμές της συνάρτησης Q (q r , x k).

Στοιχεία θεωρίας αυτομάτων

Σχέδιο:

1. Η έννοια του αυτόματου, η αρχή λειτουργίας ενός αυτόματου

2. Μέθοδοι για τον καθορισμό πεπερασμένων αυτόματα

3. Γενικά προβλήματα θεωρίας αυτομάτων

Θεωρητικές πληροφορίες

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

Η έννοια του αυτόματου, η αρχή λειτουργίας ενός αυτόματου

έννοια μηχανήεξετάζεται σε δύο πτυχές:

1. Μηχανή - συσκευήπου εκτελεί κάποιες λειτουργίες χωρίς την άμεση συμμετοχή κάποιου ατόμου. Ένα αυτόματο είναι μια πραγματική συσκευή, κατανοητό γιατί και πώς λειτουργεί, τουλάχιστον για εκείνους τους ανθρώπους που το σχεδίασαν και το κατασκεύασαν. Ένα αυτοκίνητο, ένα τρακτέρ, ένα αεροπλάνο, ένα φανάρι, μια τηλεόραση, ένα τηλέφωνο - όλα αυτά είναι αυτόματα μηχανήματα. Από αυτή την άποψη, ένας υπολογιστής θα πρέπει να γίνει κατανοητός ως ένα αυτόματο που λειτουργεί σύμφωνα με ένα πρόγραμμα που έχει καταρτιστεί από ένα άτομο.

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

Κάθε αυτόματο πρέπει να έχει έναν ορισμένο αριθμό εισόδων, έναν ορισμένο αριθμό εξόδων και έναν ορισμένο αριθμό εσωτερικών καταστάσεων.

Η θεωρία των αλγεβρικών αυτομάτων είναι ένας κλάδος της θεωρητικής κυβερνητικής που μελετά τα διακριτά αυτόματα από μια αφηρημένη αλγεβρική άποψη.

Η γενική θεωρία των αυτομάτων περιλαμβάνει διάφορες υποενότητες. Ανάλογα με το αντικείμενο μελέτης, χωρίζεται στην αφηρημένη θεωρία των αυτομάτων και στη δομική θεωρία των αυτομάτων.

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

Αντικείμενο μελέτης κατασκευαστικόςΗ θεωρία των αυτομάτων είναι η δομή του αυτόματου, καθώς και η δομή των σημάτων εισόδου και εξόδου, για παράδειγμα, μέθοδοι κωδικοποίησης σημάτων εισόδου και εξόδου κ.λπ.

Ορισμός Κρατικών Μηχανών

Μηχανή- ένα αφηρημένο μοντέλο μιας συσκευής που λειτουργεί σε διακριτό χρόνο που επεξεργάζεται μια πεπερασμένη ακολουθία σημάτων εισόδου και τα μετατρέπει σε μια πεπερασμένη ακολουθία σημάτων εξόδου (αντιδράσεις).

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

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

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

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

Ας επισημάνουμε μερικά ενδιαφέροντα ιστορικά γεγονότα που σχετίζονται με τα αυτόματα ως μηχανικές συσκευές.

1. Ο Γερμανός φιλόσοφος και αλχημιστής Αλβέρτος ο Μέγας, από το 1216 έως το 1246, δημιούργησε έναν «σιδερένιο» υπηρέτη - ένα αυτόματο που εκτελούσε τα καθήκοντα του θυρωρού στο σπίτι.

2. Ο αστρονόμος Johann Müller (Regiamontanus) (1436-1476) δημιούργησε έναν μηχανικό αετό που υποδέχτηκε την είσοδο στη Νυρεμβέργη του αυτοκράτορα Μαξιμιλιανού Β' της Αγίας Ρώμης με κλίση του κεφαλιού και κίνηση των φτερών.

3. Μηχανικός Jacques de Wacanson (1709-1782) - ο συγγραφέας του πρώτου αυτόματου αργαλειού στον κόσμο. Δημιούργησε την εικόνα μιας μηχανικής πάπιας, ένα πιστό αντίγραφο του ζωντανού ομολόγου του - κολύμπησε, καθάρισε φτερά, κατάπινε κόκκους από την παλάμη του χεριού του. Ο μηχανικός φλαουτίστας του, που ερμήνευσε έντεκα μουσικά κομμάτια, κατέπληξε τους ανθρώπους που έζησαν εκείνα τα μακρινά χρόνια.

4. Ρώσος εφευρέτης του 19ου αιώνα. Ο A. M. Gamuletsky δημιούργησε ένα ολόκληρο μηχανικό ντουλάπι, στο οποίο υπήρχαν πολλά αυτόματα σχεδιασμένα από αυτόν. Εδώ, μεταξύ άλλων, υπήρχε ένα κεφάλι ενός μάγου που μιλούσε και ένας έρωτας που έπαιζε άρπα, κάτι που κατέπληξε τη φαντασία των συγχρόνων.

5. Η πρώτη πρωτόγονη μηχανή προσθήκης σχεδιάστηκε το 1641 από τον Blaise Pascal. Το έναυσμα για το άνοιγμα ήταν το μαρτύριο του πατέρα του - ο φόρος, ένας επιθεωρητής που δούλευε μέρα νύχτα με μεγάλους υπολογισμούς. Εφευρίσκοντας μια μηχανή πρόσθεσης, ένας δεκαοκτάχρονος γιος έσωσε τον πατέρα του από πολύπλοκους υπολογισμούς και έδωσε στον κόσμο την πρώτη αριθμομηχανή που προσθέτει και αφαιρεί αριθμούς.

6. Η πρώτη σκακιστική μηχανή κατασκευάστηκε το 1890 από τον Ισπανό μηχανικό Torres Quevedo. Ένα τέτοιο αυτόματο θα μπορούσε να παίξει μόνο ένα τελικό παιχνίδι πύργου (βασιλιάς και πύργος εναντίον βασιλιά).

7. Ο πρώτος υπολογιστής με αυτόματο έλεγχο δημιουργήθηκε από τον Charles Babbage το 1822. Σχεδίασε μηχανή προσθήκης, που διέθετε μνήμη και αριθμητικές συσκευές. Αυτές οι συσκευές έγιναν πρωτότυπα παρόμοιων συσκευών σε σύγχρονους υπολογιστές.

Τύποι μηχανών.

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

Κάθε μηχανή έχει το δικό της σετ βάσης,που περιλαμβάνουν: αλφάβητο εισόδου, αλφάβητο εξόδου, σύνολο καταστάσεων αυτόματα.

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

Στη λειτουργία των πεπερασμένων ψηφιακών αυτόματα, μια σημαντική έννοια είναι χρόνος.

Τα αυτόματα μπορούν να ταξινομηθούν σύμφωνα με διάφορα κριτήρια.

1. Ανά είδος δραστηριότητας - τα αυτόματα χωρίζονται σε: πληροφορίες, έλεγχο και υπολογιστές.

Προς τηνμηχανές πληροφοριώνπεριλαμβάνει διάφορους πίνακες αναφοράς, πίνακες πληροφοριών στα γήπεδα, συσκευές συναγερμού.

Προς την μηχανήματα ελέγχουείναι σύνηθες να αποδίδονται συσκευές για τον έλεγχο μιας συγκεκριμένης διαδικασίας, συμπεριλαμβανομένων ειδικότερα: ενός ανελκυστήρα, ενός μεταφορέα, μιας εργαλειομηχανής, ενός φραγμού.

Προς την υπολογιστικές μηχανέςπεριλαμβάνουν μικροϋπολογιστές, επεξεργαστές υπολογιστών και άλλες συσκευές που εκτελούν υπολογισμούς.

Ωστόσο, αυστηρά μιλώντας, πολλά αυτόματα είναι τόσο πολύπλοκα συστήματα που είναι αυτόματα υπολογιστικά, ελέγχου και πληροφοριακά αυτόματα.

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

3. Ψηφιακές μηχανές- αυτόματα που μετατρέπουν ψηφιακόπληροφορίες. Σε ένα τέτοιο αυτόματο, τα σήματα εισόδου δίνονται ως ένα πεπερασμένο σύνολο στιγμιαίων συμβόλων: η διάρκειά τους είναι τόσο μικρή που μπορεί να παραμεληθεί. Για ένα σταθερό χρόνο, τα σύμβολα εισόδου μετασχηματίζονται και η έξοδος είναι μια μετάβαση από μια κατάσταση σε μια άλλη κατάσταση.

4. Αφηρημένα αυτόματα -εμφάνιση ενός συνόλου λέξεων στο αλφάβητο εισαγωγής Χσεσύνολο λέξεων αλφαβήτου εξόδου Υ.

Το αφηρημένο αυτόματο είναι:

~ Μαθηματικόςμοντέλο,

~ Αλγόριθμοςενέργειες κάποιου μετασχηματισμού αλληλουχιών κώδικα,

~ Νόμοςμετατροπές του αλφαβήτου εισόδου σε αλφάβητο εξόδου.

5. Σύγχρονα και ασύγχρονα αυτόματα. Ανάλογα με το εάν το σήμα εισόδου και το σήμα αλλαγής κατάστασης λαμβάνονται ταυτόχρονα ή διαδοχικά, τα αυτόματα χωρίζονται σε σύγχρονα και ασύγχρονα αυτόματα.

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

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

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

Κάτω από το ατελείωτοΤο αυτόματο συνήθως κατανοείται ως μια ορισμένη μαθηματική εξιδανίκευση ιδεών για ένα αυτόματο που έχει άπειρο αριθμό καταστάσεων. Η μνήμη ενός τέτοιου αυτομάτου μπορεί ενδεχομένως να μεγαλώσει επ' αόριστον. Για παράδειγμα, τα περίφημα αφηρημένα αυτόματα αυτόματα Post και Turing είναι άπειρα αυτόματα, αλλά ο ίδιος ο υπολογιστής ή τα επιμέρους μέρη του είναι πεπερασμένα αυτόματα.

7. Τα αυτόματα χωρίζονται σε ντετερμινιστικά και πιθανοτικά αυτόματα. Εάν η ταξινόμηση βασίζεται σε μηχανισμός τυχαίας επιλογήςτότε γίνεται διάκριση μεταξύ ντετερμινιστικών και πιθανοτικών (στοχαστικών) αυτόματα.

Σε ντετερμινιστικά αυτόματαη συμπεριφορά και η δομή σε κάθε χρονική στιγμή καθορίζονται μοναδικά από τις τρέχουσες πληροφορίες εισόδου και την κατάσταση του ίδιου του αυτόματου την προηγούμενη χρονική στιγμή.

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

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

8. Μηχάνημα Universal.Στη θεωρία των αυτομάτων, αποδεικνύεται ότι για να πραγματοποιηθούν διάφοροι μετασχηματισμοί πληροφοριών, αρκεί η κατασκευή Παγκόσμιοςαυτόματο μηχάνημα με τη βοήθεια προγράμματος και κατάλληλης κωδικοποίησης, ικανό να λύσει τυχόν προβλήματα.

Το μαθηματικό μοντέλο ενός ψηφιακού αυτόματου με μία είσοδο δίνεται από πέντε αντικείμενα:

Χ-πεπερασμένο σύνολο συμβόλων εισαγωγής, αλφάβητο εισόδου:

X \u003d (x 1 (t), x 2 (t), ..., x n (t));

Υ-πεπερασμένο σύνολο συμβόλων εξόδου, αλφάβητο εξόδου:

Y \u003d (y 1 (t), y 2 (t), ..., y n (t));

Q~πεπερασμένο σύνολο καταστάσεων αυτόματα:

Q= (q 0 (t), q 1 (t), q 2 (t), …, q n (t)), q0- αρχική κατάσταση;

δ(q, Χ) - η λειτουργία της μετάβασης του αυτόματου από τη μια κατάσταση στην άλλη: ( QΧ Χ)®Q;

λ(q, Χ) ~ λειτουργία αυτόματης εξόδου: ( Qχ Χ) ® Υ.

Η κρατική μηχανή λοιπόν C=(X, Q,Υ, δ, λ.) καθορίζεται από τις αναδρομικές σχέσεις

q(0) = q 0, q(t + I) = δ (g(t), x(t)), y(t) = λ (g(t), x(t)),

t είναι η διακριτική στιγμή του χρόνου ή είναι η εικόνα μιας μονότονης συνάρτησης t:. Τ® Ν, και T -συνήθης συνεχής χρόνος, Ν είναι το σύνολο των φυσικών αριθμών.

Όλες οι ώρες εργασίας Τχωρίζεται σε πεπερασμένο αριθμό διαστημάτων, στο όριο των οποίων αλλάζει η κατάσταση του αυτόματου. Ταυτόχρονα, το t(Г 0) δείχνει τον αριθμό των αλλαγών που έχουν συμβεί πριν από το χρόνο Г 0 .

Ένα παράδειγμα διακριτοποίησης είναι ο συνηθισμένος κινηματογράφος: ο χρόνος χωρίζεται σε διαστήματα 1/24 δευτερολέπτων. Το ανθρώπινο μάτι αντιλαμβάνεται την παρακολούθηση διακριτών πλαισίων ως συνεχή κίνηση.

9. Τα σύγχρονα αυτόματα χωρίζονται σε αυτόματα Mealy και σε αυτόματα Moore. Εξαρτάται από τρόπο οργάνωσης της λειτουργίας εξόδουοι σύγχρονες μηχανές χωρίζονται σε μηχανές Mealy (αυτόματα πρώτου είδους) και αυτόματα Moore (αυτόματα δεύτερου είδους).

Στα μηχανήματα αυτόματης πώλησης Mili- σήμα εξόδου y(t) Χ(t)και κράτος q(t- 1) το αυτόματο την προηγούμενη χρονική στιγμή (t-ένας). Το μαθηματικό μοντέλο τέτοιων αυτόματα είναι το σύστημα εξισώσεων:

q(t) = δ (q(t-1), x(t)) και y(t) = λ (q(t-1), x(t)),

Σε μηχανές Mooreσήμα εξόδου y(t)καθορίζεται μοναδικά από το σήμα εισόδου Χ(t)και κράτος q(t)σε μια δεδομένη χρονική στιγμή t. Το μαθηματικό μοντέλο τέτοιων αυτόματα είναι το σύστημα:

q(t) = δ (q(t-1), x(t)) και y(t) = λ (q(t)),

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

10. Συνδυαστικά αυτόματα– υπάρχουν αυτόματα στα οποία το σύμβολο εξόδου δεν εξαρτάται από την κατάστασή του και καθορίζεται μόνο από τα τρέχοντα σύμβολα εισόδου, π.χ. σε αυτό το αυτόματο όλες οι καταστάσεις είναι ισοδύναμες. Σε ένα τέτοιο αυτόματο, η λειτουργία μετάβασης είναι εκφυλισμένη, είναι ουσιαστικά ασήμαντη και αμετάβλητη κατά τη λειτουργία. Επομένως, το ελάχιστο συνδυαστικό αυτόματο έχει μόνο μία κατάσταση.

11 Booleanαυτόματα - υπάρχουν αυτόματα τα οποία το αλφάβητο εισόδου αποτελείται από 2 τδυαδικά σύνολα μήκους t,και η έξοδος είναι από 2 n δυαδικά σύνολα μήκους Π.Για λογική συνδυαστικήαυτόματα, η συνάρτηση εξόδου έχει τη μορφή συστήματος Π λογικές συναρτήσεις από tμεταβλητές.

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

Στο κανάλι εισόδου ανά πάσα στιγμή t =1, 2, ... στη συσκευή Μ φτάνουν σήματα εισόδου (από κάποιο πεπερασμένο σύνολο σημάτων). Ο νόμος της αλλαγής κατάστασης στην επόμενη χρονική στιγμή ρυθμίζεται ανάλογα με το σήμα εισόδου και την κατάσταση της συσκευής την τρέχουσα χρονική στιγμή. Το σήμα εξόδου εξαρτάται από την κατάσταση και το σήμα εισόδου την τρέχουσα ώρα (Εικ. 1).

Η μηχανή κατάστασης είναι ένα μαθηματικό μοντέλο πραγματικών διακριτών συσκευών επεξεργασίας πληροφοριών.

κρατική μηχανή ονομάζεται το σύστημα Α= (Χ , Q , Υ ,  ,  ), όπου Χ , Q , Υ είναι αυθαίρετα μη-κενά πεπερασμένα σύνολα, και  και  - λειτουργίες, εκ των οποίων:

πολλά Χ ={ένα 1 , ..., ένα Μ ) λέγεται αλφάβητο εισαγωγής , και τα στοιχεία του είναι σήματα εισόδου , οι ακολουθίες τους είναι μέσα συνθηματικές φράσεις ;

πολλά Q ={q 1 , ..., q n ) λέγεται πολλά κράτη αυτόματο και τα στοιχεία του - πολιτείες ;

πολλά Υ ={σι 1 , ..., σι Π ) λέγεται αλφάβητο εξόδου , τα στοιχεία του είναι σήματα εξόδου , οι ακολουθίες τους είναι λέξεις εξόδου ;

λειτουργία  : Χ  Q Q που ονομάζεται λειτουργία μετάβασης ;

λειτουργία  :Χ  Q Υ που ονομάζεται λειτουργία εξόδου .

Με αυτόν τον τρόπο,  (Χ , q )Q ,  (Χ , q )Υ για  Χ Χ , q Q .

Μια φανταστική συσκευή συνδέεται με τη μηχανή κατάστασης, η οποία λειτουργεί ως εξής. Μπορεί να είναι σε κατάσταση από το σετ Q , λάβετε σήματα από το σετ Χ και εκδίδουν σήματα από ένα σετ Υ .

2. Μέθοδοι για τον ορισμό ενός πεπερασμένου αυτόματου

Υπάρχουν αρκετοί ισοδύναμοι τρόποι για τον ορισμό των αφηρημένων αυτόματα, τρεις από τους οποίους είναι: πινακοειδής , γεωμετρικός και λειτουργικός .

2.1 Αντιστοίχιση πίνακα του μηχανήματος

Από τον ορισμό του αυτόματου προκύπτει ότι μπορεί πάντα να οριστεί από έναν πίνακα με δύο εισόδους που περιέχει t γραμμές και Π στήλες, όπου στη διασταύρωση της στήλης q και γραμμές ένα αξίζουν οι τιμές συνάρτησης  (ένα Εγώ , q ι ),  (ένα Εγώ , q ι ).

2.2. Ορισμός αυτόματου με διάγραμμα Moore

Ένας άλλος τρόπος καθορισμού μιας μηχανής πεπερασμένης κατάστασης είναι ο γραφικός, δηλαδή η χρήση γραφήματος. Το αυτόματο αναπαρίσταται ως ένα επισημασμένο κατευθυνόμενο γράφημα σολ(Q , ρε ) με πολλές κορυφές Q και πολλά τόξα ρε ={(q ι ,  (ένα Εγώ , q ι ))| q ι Q , ένα Εγώ Χ ), ενώ το τόξο ( q ι ,  (ένα Εγώ , q ι )) επισημαίνεται με ένα ζευγάρι ( ένα Εγώ ,  (ένα Εγώ , q ι )). Έτσι, με αυτή τη μέθοδο, οι καταστάσεις του αυτόματου απεικονίζονται με κύκλους, στους οποίους εισάγονται τα σύμβολα των καταστάσεων q ι (ι = 1, …, n ). Από κάθε κύκλο πραγματοποιείται t βέλη (κατευθυνόμενες άκρες) ένα προς ένα που αντιστοιχούν στους χαρακτήρες του αλφαβήτου εισόδου Χ ={ένα 1 , ..., ένα Μ ). Βέλος που αντιστοιχεί στο γράμμα ένα Εγώ Χ και φεύγοντας από τον κύκλο q ι Q , το ζεύγος ( ένα Εγώ ,  (ένα Εγώ , q ι )), και αυτό το βέλος οδηγεί σε έναν κύκλο που αντιστοιχεί σε  (ένα Εγώ , q ι ).

Το σχέδιο που προκύπτει ονομάζεται αυτόματο γράφημα ή, Διάγραμμα Moore . Για όχι πολύ περίπλοκα αυτόματα, αυτή η μέθοδος είναι πιο ενδεικτική από ό πινακοειδής.

Συνιστούμε να διαβάσετε

Υδραυλικά

Δύο δοκιμές έδειξαν δύο λωρίδες: την αρχή του τεστ εγκυμοσύνης, οδηγίες χρήσης, αποτέλεσμα, υπερηχογράφημα και διαβούλευση με γυναικολόγο Τι να κάνετε το τεστ δείχνει δύο ταινίες

Επιπλα

Πότε να εγγραφείτε για εγκυμοσύνη: συγκεκριμένες ημερομηνίες και ανάγκη εγγραφής

Επιπλα

Τι πέφτει σε μια μύτη που. Τύποι ρινικών σταγόνων. Σταγόνες παντζάρι από το κοινό κρυολόγημα

Εξοχικό σπίτι

Ποιος είναι ο λόγος της συνεχούς επιθυμίας για ποτό;

Ταπετσαρία

Κεντρικό σύστημα βιβλιοθηκών της περιοχής Khaibullinsky της Δημοκρατίας του Μπασκορτοστάν Bianka Igor Kubersky

Φινίρισμα

Κατσικίσιο τυρί στο σπίτι συνταγή με φωτογραφία βήμα προς βήμα