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 two 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 π and πk respectively. The elements of πk 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: πn = πn+1 for some n. (πn denotes the set of equivalence classes under n-equivalence.)