Μια κρατική μηχανή είναι απλά ένα άλλο όνομα για ένα πεπερασμένο αυτόματο . Πρόκειται για μια συλλογή των διαφόρων κρατών που συνεργάζονται για την επίτευξη του στόχου επιθυμία του συγκεκριμένο έργο . Για παράδειγμα , θα μπορούσατε να δημιουργήσετε μια κρατική μηχανή για να προσδιορίσει αν ένα string αντιπροσωπεύει μια συγκεκριμένη λέξη . Εισάγοντας τη λέξη , ας πούμε τη λέξη « πρόσωπο », θα ξεκινήσει η διαδικασία της κρατικής μηχανής .
Εικόνων Πολιτείες
μελών αντιπροσωπεύει ένα διαφορετικό στάδιο της διαδικασίας . Για τη λέξη - αναγνωρίζοντας πεπερασμένο αυτόματο του τελευταίου τμήματος , το πρώτο , ή το αρχικό στάδιο είναι το αρχικό στάδιο , όπου θα μπορούσαμε να κοιτάξουμε για το πρώτο γράμμα του επιθυμητού λέξη . Για αυτό το παράδειγμα , το αρχικό στάδιο θα είναι το γράμμα « ρ », το πρώτο γράμμα της λέξης "πρόσωπο . " Αν το πρώτο γράμμα είναι το " p ", τότε το πρώτο κράτος έχει φτάσει και το πεπερασμένο αυτόματο έχει εμπλακεί .
Η Μεταβάσεις
Η
Μεταβάσεις συνδέουν τα κράτη της πεπερασμένα αυτόματα . Για να πάρετε σε κάθε νέο διαδοχική κατάσταση , ένα ακίνητο πρέπει να βρεθεί για να είναι αληθινό . Για παράδειγμα , η απαιτούμενη μετάβαση είναι ότι το επόμενο γράμμα είναι το γράμμα "e ". Εάν το γράμμα " e" είναι όντως το επόμενο γράμμα , τότε η είσοδος ταξιδεύει στην επόμενη κατάσταση . Η είσοδος στη συνέχεια θα ελεγχθούν στα ακόλουθα κράτη , και κάθε φορά που η είσοδος πληροί την απαραίτητη προϋπόθεση του κράτους , θα μετάβαση έως ότου επιτευχθεί η τελική κατάσταση ή η είσοδος αποδειχθεί ψευδής .
Εικόνων προσδιοριστικών και μη-αιτιοκρατικός
Η
Η κρατική μηχανή που περιγράφεται στην προηγούμενη ενότητα είναι ένα ντετερμινιστικό πεπερασμένο αυτόματο , στην οποία κάθε κράτος είναι μοναδικό . Τι θα κάνει ένα πεπερασμένο αυτόματο nondeterministic είναι αν κάθε κράτος δεν ήταν . Για παράδειγμα , αν η κρατική μηχανή επιτρέπεται η είσοδος να έχει κάποια επιστολή ως το δεύτερο γράμμα της λέξης "πρόσωπο" για τη μετάβαση στην επόμενη , τότε η επόμενη κατάσταση δεν θα είναι μοναδικό , καθιστώντας το ένα πεπερασμένο αυτόματο nondeterministic .
Η
Πνευματικά δικαιώματα © Γνώση Υπολογιστών Όλα τα δικαιώματα κατοχυρωμένα