Στο πρόβλημα αυτό πρέπει να φτιαχτεί ένα πρόγραμμα που κατασκευάζει ενά ελάχιστο DFA από ένα δοσμένο DFA. Ένα DFA (Discrete Finite Automaton) που θα εξετάσουμε εδώ είναι μια μηχανή η οποία αποδέχεται ή όχι συμβολοακολουθίες. Ένα DFA αποτελείται από ένα πεπερασμένο αριθμό καταστάσεων και μια συνάρτηση μετάβασης. Μερικές από τις καταστάσεις είναι τελικές. Υπάρχει μια αρχική κατάσταση, από την οποία ξεκινά τη λειτουργία του το αυτόματο. Σε κάθε βήμα το αυτόματο διαβάζει ένα χαρακτήρα από τη συμβολοακολουθία που ελέγχουμε και αναλόγως του χαρακτήρα και της κατάστασης που βρίσκεται, μεταπηδά σε μια νέα κατάσταση (όχι απαραίτητα διαφορετική). Ο ακριβής τρόπος δίνεται από τη συνάρτηση μετάβασης ή ένα πίνακα. Αν η συμβολοακολουθία τελειώσει όταν το αυτόματο βρίσκεται σε τελική κατάσταση, το αυτόματο "αποδέχεται" τη συμβολοακολουθία, αλλιώς δεν την αποδέχεται. Ισοδύναμα λέγονται δυο DFA όταν αναγνωρίζουν τις ίδιες ακριβως συμβολοακολουθίες. Ελάχιστο ισοδύναμο DFA ενός αυτομάτου είναι αυτό που είναι ισοδύναμο και έχει τον ελάχιστο αριθμό καταστάσεων.

Για να κατασκευάσουμε το ελάχιστο DFA πρέπει σταδιακά να ενοποιήσουμε τις όμοιες καταστάσεις, δηλ. αυτές που είναι του ίδιου τύπου (τελικές ή μη) και ταυτόχρονα με την ίδια είσοδο πηγαίνουν στην ίδια επόμενη κατάσταση.

Πχ. ένα αυτόματο που αναγνωρίζει συμβολοακολουθίες από a kai b που έχουν περιττό αριθμό b είναι το εξής (τελικές καταστάσεις με διπλή γραμμή):

+---+  a   +---+
|   | ---->|   | --+
| 0 | -+   | 1 |   |a
|   |  |   |   | <-+
+---+  |   +---+
       |    Λ |
       |   b| |b
      b|    | |
       |    | V
       |   #####
       +-->#   # <--+
           # 2 #    |a
	   #   # ---+
	   #####

    +---+  b   #####
 +--|   | ---> #   # ---+
a|  | 0 |      #   #    |a
 +->|   | <--- #   # <--+
    +---+  b   #####

3
a b
2
a:1 b:2
a:1 b:2
a:2 b:1

2