Skip to main content

7. Minimisation of Finite Automata

23/02/23

Regular language is

  • The language of a regular expression
  • The language of a NFA
  • The language of a DFA

When converting NFAs into DFAs, they're not always in their simplest form. Because the minimal DFAs are unique, the languages are equal if and only iff the minimal DFAs are equal.

If two states are not equivalent, then they are distinguishable

The table-filling algorithm recursively constructs the set of distinguishable pairs of state for a DFA. When all distinguishable state pairs have been identified, any remaining pairs of states must be equivalent. Such states can be merged, thereby minimising the automation.