DHARMREGULAR AND NONREGULAR LANGUAGES 267
10.5.5 Minimization Problem and Myhill Nerode Theorem (Optimizing DFA)........
The Minimization problem suggest the way that how we will find a minimum state DFA equiva-
lent to given DFA. Since there is essentially an unique minimum state DFA for every regular
expression Myhill Nerode theorem.
Recall the discussion of equivalence relations and equivalence classes from section 1.4.
Assume L be an arbitrary language and RL be an equivalence relation i.e., x RLy if and only if
for each a, either both xa and ya ∈ L or neither is in L. Alternatively the number of equivalence
classes is always finite if L is a regular language. Associated with the finite automaton there
exists also a natural equivalence relation on its language set i.e., for any x, y ∈ Σ, x RLy if and
only if δ(q 0 , x) = δ(q 0 , y). The relation RL divides the set Σ into equivalence classes which is
finite. In addition, if x RLy, then xa RL ya for all a ∈Σ. An equivalence relation RL such that
xRLy = xa RL ya is said to be right invariant with respect to concatenation. Later we will see
that every FAs make a right invariant equivalence relation on its language set.
(Myhill Nerode theorem)
If L be a regular language then the set of equivalence classes of RL is finite.
Alternatively the set L ∈ Ζ is accepted by some FA, and let EL be the set of equivalence
classes of the relation RL on Σ*. If EL is a finite set then a FA accepts L provided that this FA has
the fewest states then any FA accepting L. Besides other consequences of this theorem, its impli-
cation is that there exists always a unique minimum state DFA for any regular language.
This suggests that from a given DFA some/more of the states might be equivalent or
they are not distinguishable. All such states are form a group and placed in a class. So, the
partitions of states are grouped into two different classes. One is the equivalence class of
states and other is the class of distinguishable states. The transition nature of the class is
similar to the transition of individual states in the group. So, these classes are equivalent to
the different states of the DFA and we get minimum states DFA. (number of states would be
less than the number of states of given DFA).
Finding equivalence of states
Assume DFA M = (Q, Σ, δ, q 0 , F) and let r and s are the states ∈ Q then, States r and s are said
to be equivalent if for all strings x of L have:
l δ$(r, x) ∈ F and δ$(s, x) ∈ F (for ∀x ∈ L).
States r and s are said to be distinguishable if for at least a string x ∈ L have:
l δ$(r, x) ∈ F and δ$(s, x) ∉ F; or
l δ$(r, x) ∉ F and δ$(s, x) ∈ F; or
l δ$(r, x) ∉ F and δ$(s, x) ∉ F; (where F is the set of accepting state/s).
The equivalence of states have been categorized into various classes which is depend
upon up to what extents of symbols of string x they behaves in similar nature (returns on the
set F). These equivalence classes are 0-equivalence class, 1-equivalence class, 2-equivalence
class,......k-equivalence class.
k-equivalence class
Let states r and s ∈ Q then r and s are k-equivalent states if and only if no string of length ≤ k
can distinguish them. It says that, for all strings of length k or smaller up to zero (because
symbol ∈ has length 0) transition of states r and s reaches to final state.