Ντετερμινιστικό πεπερασμένο αυτόματο
From Wikipedia, the free encyclopedia
Το ντετερμινιστικό πεπερασμένο αυτόματο (deterministic finite state automaton ή DFA) είναι ένα υπολογιστικό μοντέλο, ένας εξιδανικευμένος νοητός υπολογιστής αποτελούμενος από έναν πεπερασμένο αριθμό καταστάσεων και μια συνάρτηση μετάβασης, μέσω της οποίας καθορίζονται οι μεταβάσεις από κατάσταση σε κατάσταση, ανάλογα με την είσοδο που δέχεται το αυτόματο. Η έξοδος του αυτόματου θα είναι είτε αποδοχή είτε απόρριψη της εισόδου.
Το λήμμα παραθέτει τις πηγές του αόριστα, χωρίς παραπομπές. |
Επειδή οι καταστάσεις του αυτόματου είναι πεπερασμένου πλήθους και επειδή μέσω της συνάρτησης μετάβασης το αυτόματο μεταβαίνει σε μία μόνο κατάσταση, δηλαδή δεν υπάρχουν πάνω από μία επιλογές, το συγκεκριμένο υπολογιστικό μοντέλο είναι πεπερασμένο και ντετερμινιστικό.
Τα ντετερμινιστικά πεπερασμένα αυτόματα αποτελούν μια κατηγορία των πεπερασμένων αυτόματων. Αναγνωρίζουν μόνο κανονικές γλώσσες.