DFA Minimization - Minimum DFA

Minimum DFA

For each regular language that can be accepted by a DFA, there exists a minimal automaton, a DFA with a minimum number of states and this DFA is unique (except that states can be given different names.) The minimal DFA ensures minimal computational cost for tasks such as pattern matching.

There are two classes of states that can be removed/merged from the original DFA without affecting the language it accepts to minimize it.

  • Unreachable states are those states that are not reachable from the initial state of the DFA, for any input string.
  • Nondistinguishable states are those that cannot be distinguished from one another for any input string.

DFA minimization is usually done in three steps, corresponding to the removal/merger of the relevant states. Since the elimination of nondistinguishable states is computationally the most expensive one, it is usually done as the last step.

Read more about this topic:  DFA Minimization

Famous quotes containing the word minimum:

    After decades of unappreciated drudgery, American women just don’t do housework any more—that is, beyond the minimum that is required in order to clear a path from the bedroom to the front door so they can get off to work in the mourning.
    Barbara Ehrenreich (20th century)