DFA minimization

avatar
Created by
Francisca Portugal

Cards (2)

  • DFA MINIMIZATION
    It is possible to find a minimum representation in terms of the number of states for a given language
    1. Use the table-felling algorithm to nd all the pairs of equivalent states
    2. Partition the set of states into groups of equivalent states (the state equivalence is transitive)
    3. Consider each group a state and modify accordingly
    4. The start state is the block containing the original start state
    5. The set of accepting states is the set of blocks containing accepting states from the original automaton
  • EXAMPLE