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 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 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: π_n = π_n+1 for some n. (π_n denotes the set of equivalence classes under n-equivalence.)