Minimization of Finite Automata
Minimization of DFA:
we construct an automaton with the minimum number of states equivalent to a given automaton M.
As our interest lies only in strings accepted by M, what matters is whether a state is a final state or not. We define some relations in Q.
DefInition-1: Two states q1 and q2 are equivalent (denoted by q1 == q2) if both δ(q1, x) and δ(q2, x) are final states. or both of them are nonfinal states for all x∈ ∑*.
As it is difficult to construct δ(q1, x) and δ(q2, x) for all x ∈ ∑* (there are an infinite number of strings in ∑*). we give one more definition.
Definition-2: Two states q1 and q2 are k-equivalent (k ;::: 0) if both δ(q1, x) and δ(q2, x) are final states or both nonfinal states for all strings x of length k or less. In particular, any two final states are 0-equivalent and any t\VO nonfinal states are also 0-equivalent.
We mention some of the properties of these relations.
Property-1: The relations we have defined. i.e. equivalence and k-equivalence, are equivalence relations. i.e. they are reflexive, symmetric and transitive.
Property-2: By Theorem 2.1. these induce partitions of Q. These partitions can be denoted by Jr and Jrl’ respectively. The elements of Jul are k-equivalence classes.
Property-3: If q1 and q2 are k-equivalent for all k;::: O. then they are equivalent.
Property-4: If q1 and q2 are (k + I)-equivalent. then they are k-equivalent.
Property-5: ir” =Jr,,+] for some 11. (Jr” denotes the set of equivalence classes under l1-equivalence.)