Mathematical Foundation of Computer Science

DHARM

268 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

We say that equivalence relation RK exists between states r and s (pRKq). So, to distinguish
the states on these bases and make partition, this partition of states is called k-equivalence
classes.
Similarly we can define other equivalence classes.

0-equivalence class

Test the equivalence relation such as rR 0 s for the string of length 0(Ignore the mean-

ingless case of length less than 0). It means we are talking about the string containing symbol

∈ (| ∈ | = 0) only. If both δ(r, ∈) ∈ F and δ(s, ∈) ∈ F, then states r and s are said to

be 0-equivalent states, and partition of states is 0-equivalent classes.

1-equivalence class

Similarly test the equivalence relation rR 1 s for the string of length one or zero (i.e. length ≤ 1).

Assume language L is define over Σ, where Σ = {0, 1} then test the relation rR 1 s over symbols

0, 1 and ∈ only and make partition of states.

Example 10.6. Let the Language L = {x ∈ {0, 1}*/the second symbol from the right is a 1} then

the corresponding regular expression is (0 + 1)*. 1. (0 + 1) and the possible DFA that accepts

above regular expression is shown in Fig. 10.11.

P

R

Q

0

1 0

1

1

0

S 11 T 10 U 01

1

0

(^1) V 00
0
(^10)
1 0
Fig. 10.11. (M)
Now, Is this is a minimum states DFA M? If not, then construct the minimum states
DFA.
Where, M = ({P, Q, R, S, T, U, V}, {0, 1}, δ, {P}, {S, T})
Sol. Find equivalence classes
0-equivalence classes
Test the transition of states over the symbol ∈ and make groups of the states which are equiva-
lent and which are distinguishable.
Since, PR 0 Q ⇒δ(P, ∈) = P(∉ F) and δ(Q, ∈) = Q(∉ F) so they are
Distinguishable.
And, PR 0 R ⇒δ(P, ∈) = P(∉ F) and δ(R, ∈) = R(∉ F) so they are
Distinguishable.