Επεξήγηση μηχανή πεπερασμένης κατάστασης

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

Κατανόηση της μηχανής πεπερασμένων καταστάσεων

Ένα FSM ορίζεται από τις καταστάσεις του , την αρχική του κατάσταση και τις μεταβάσεις .

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

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

Διάγραμμα κατάστασης

Διάγραμμα πεπερασμένης κατάστασης μηχανής καφέ

Αυτό το διάγραμμα δείχνει τρεις πιθανές καταστάσεις για τη μηχανή καφέ:

  • Ανοιξε
  • ReadyToBuy
  • PoweredOff

Οι γραμμές μεταξύ αυτών των καταστάσεων δείχνουν ποιες μεταβάσεις είναι δυνατές μεταξύ καταστάσεων και προς ποια κατεύθυνση. Αυτές οι μεταβάσεις έχουν προϋποθέσεις για το πότε το FSM πρέπει να αλλάξει μεταξύ των καταστάσεων.

  • StartUpMachine Από την κατάσταση PoweredOff στην κατάσταση Open, το μηχάνημα πρέπει να ξεκινήσει. Αυτό γίνεται χειροκίνητα σε αυτήν την περίπτωση.
  • κατάθεση> = κόστος καφέ Το FSM αξιολογεί το ποσό των κατατεθέντων μετρητών είτε σε ένα βρόχο είτε όταν αλλάζει το ποσό (συνιστάται σε αυτήν την περίπτωση) Εάν καταθέσετε αρκετά μετρητά στη μηχανή καφέ, το FSM θα μεταβεί από το «Open» στο «ReadyToBuy» ".
  • ShutdownMachine Το μηχάνημα θα μεταβεί αυτόματα από το Open στο PoweredOff μέσω της μεθόδου ShutDownMachine εάν πληρούται η προϋπόθεση «δεν υπάρχουν άλλοι καφέδες».
  • DispenseCoffee Στην κατάσταση ReadyToBuy ο χρήστης μπορεί να αγοράσει έναν καφέ και στη συνέχεια θα παρασκευαστεί και θα διανεμηθεί. Η προϋπόθεση είναι όταν ενεργοποιείται το συμβάν BuyCoffee (! Σύνδεσμος για μοτίβο παρατηρητή!). (δεν φαίνεται στο διάγραμμα)
  • Ακύρωση καφέ Εάν ο χρήστης επιλέξει να ακυρώσει, το μηχάνημα θα μεταβεί από το ReadyToBuy στο Open.
  • ShutDownMachine Το μηχάνημα θα μεταβεί στην κατάσταση PoweredOff

Κράτη

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

Αρχική κατάσταση

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

Μεταβάσεις

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

DFA και NFA

Υπάρχουν δύο τύποι πεπερασμένων αυτόματων, Ντετερμινιστική (DFA) και Nondeterministic (NFA). Και οι δύο αποδέχονται κανονικές γλώσσες και λειτουργούν λίγο πολύ με τον ίδιο τρόπο που περιγράφεται παραπάνω, ωστόσο με κάποιες διαφορές.

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

  1. Κάθε μία από τις μεταβάσεις της καθορίζεται μοναδικά από την κατάσταση προέλευσης και το σύμβολο εισόδου
  2. Απαιτείται ανάγνωση ενός συμβόλου εισόδου για κάθε μετάβαση κατάστασης.

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

Λοιπόν, τι είδους κανόνες μπορούμε να περιμένουμε να βρούμε στα NFA αλλά όχι στα DFA;

  1. Ένα NFA μπορεί να έχει μια κενή μετάβαση συμβολοσειράς (γενικά συμβολίζεται με ένα epsilon). Αυτό σημαίνει ότι όταν σε μια συγκεκριμένη κατάσταση με ένα epsilon για έναν κανόνα μετάβασης, το μηχάνημα μπορεί να μεταβεί στην επόμενη κατάσταση χωρίς να διαβάσει ένα σύμβολο εισόδου
  2. Σε ένα NFA, κάθε ζεύγος κατάστασης και σύμβολο μετάβασης μπορεί να έχει πολλές καταστάσεις προορισμού σε αντίθεση με τους μοναδικούς προορισμούς ζευγών σε DFA
  3. Κάθε ζεύγος συμβόλου κατάστασης και μετάβασης παράγει έναν «κλάδο» υπολογισμού για καθένα από τους πιθανούς προορισμούς του δημιουργώντας ένα είδος ενός πολυήματου συστήματος.
  4. Ένα DFA θα απορρίψει τη συμβολοσειρά εισόδου εάν προσγειωθεί σε οποιαδήποτε άλλη κατάσταση εκτός από την κατάσταση αποδοχής. Σε ένα NFA, χρειαζόμαστε μόνο ένα «υποκατάστημα» για να φτάσουμε σε μια κατάσταση αποδοχής για να αποδεχτούμε τη συμβολοσειρά.

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