Mathematical Foundation of Computer Science

DHARM

REGULAR AND NONREGULAR LANGUAGES 269

And, PR 0 S ⇒δ(P, ∈) = P(∉ F) and δ(S, ∈) = S(∉ F) so they are
Distinguishable.
Similarly test all other states with each other we find states P, Q, R, U and V are distin-
guishable so, they form a group:
{P, Q, R, U, V}
Only states S and T are equivalence, because
SR 0 T ⇒δ(S, ∈) = S(∈ F) and δ(T, ∈) = T(∈ F)so they are
Equivalence and form another group {S, T}
Hence, 0-equivalence classes are,
{P, Q, R, U, V} and {S, T}

1-equivalence classes

Test the equivalence relation between states of groups for the strings of length less then or
equal to one (i.e. for the symbols ∈, 0 and 1).
First take up the group of states {P, Q, R, U, V} and test for equivalence,
Symbol ∈ is not able to distinguish between states of above group so, test equivalence
with respect to another symbols 0 and 1.
PR 1 Q ⇒δ(P, 0/1) = R/Q(∉ F) and δ(Q, 0/1) = T/S(∈ F)so they are
Distinguishable.
And, PR 1 R ⇒δ(P, 0/1) ∉ F and δ(R, 0/1) ∉ F; so they are distinguishable.
And, PR 1 S ⇒δ(P, 0/1) ∉ F and δ(S, 0/1) ∈ F; so they are distinguishable.
And, PR 1 U ⇒δ(P, 0/1) ∉ F and δ(U, 0/1) ∈ F; so they are distinguishable.
And, PR 1 V ⇒δ(P, 0/1) ∉ F and δ(V, 0/1) ∉ F; so they are distinguishable.
Similarly test for other pairs of states in this group, we find states Q and U are equivalent
because,
QR 1 U ⇒δ(Q, 0/1) ∈ F and δ(U, 0/1) ∈ F; so they places in other group.
Test equivalence relation for other group of states {S, T}, we see that
SR 1 T ⇒δ(S, 0/1) ∈ F and δ(T, 0/1) ∉ F; since they are distinguishable
so they will not be in the same group.
Hence 1-equivalence classes are,
{P, R, V}, {Q, U}, {S} and {T}
(this is a refinement of 0-equivalence class)
2-equivalence classes
Now test the equivalence relation for the strings ε, 0,1,00,01,10,11 (all strings of length ≤ 2).
Since we form the groups of states w.r.t. strings ε, 0, and 1 so further it can not be distinguish.
Now test the equivalence relation between states of the groups only the over remaining strings.
We say it xy, where x and y are either 0 or 1.
Since,
PR 2 R ⇒δ(P, 00/01) ∉ F and δ(R, 00/01) ∉ F; so they are distinguishable.
And, PR 1 V ⇒δ(P, 00/01) ∉ F and δ(V, 00/01) ∉ F; so they are distinguishable.
And, RR 1 V ⇒δ(R, 00/01) ∉ F and δ(V, 00/01) ∉ F; so they are distinguishable.