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 q₁ and q₂ are equivalent (denoted by q₁ == q₂) if both δ(q₁, x) and δ(q₂, x) are final states. or both of them are nonfinal states for all x∈ ∑*.

As it is difficult to construct δ(q₁, x) and δ(q₂, x) for all x ∈ ∑* (there are an infinite number of strings in ∑*). we give one more definition.

Definition-2: Two states q₁ and q₂ are k-equivalent (k ;::: 0) if both δ(q₁, x) and δ(q₂, 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 q₁ and q₂ are k-equivalent for all k;::: O. then they are equivalent.

Property-4: If q₁ and q₂ 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.)