Mathematical Foundation of Computer Science

DHARM

270 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

Since, we couldn’t find any equivalent of states in this group so there is no split in the
group.
Next, test for equivalence in other group {Q, U}.
QR 1 U⇒δ(Q, 00/01) ∉ F and δ(U, 00/01) ∉ F; so they are distinguishable.
So there is no split in this group also.
Since, group {S} and {T} contains single state so further there is no split in these groups.
Hence, 2-equivalence classes are,
{P, R, V}, {Q, U}, {S} and {T}
That is similar to 1-equivalence classes and since there is no further refinement. So,
process to find equivalence classes terminate.
Hence, equivalent states are ⇒ {P, R, V}, {Q, U}, {S} & {T}
Therefore, minimum state DFA has just above 4-states.
Remember transition nature of groups is given by the transitions of all the states in the
group that return on the same group or some other group. Thus we obtain the transition table
shown in Fig. 10.12.

State

Input Symbol

01

{P, R, V} Return on same group {P, R, V} Return on group {Q, U}

{Q, U} Return on group {T} Return on group {S}

{T} Return on group {V} Return on group {U}

{S} Return on group {T} Return on group {S}

Fig. 10.12

And the minimum states DFA is shown in Fig. 10.13 :

[whose language is also the language expressed by the regular expression

(0 + 1)*. 1. (0 + 1)]

{P, R, V}

T

S

{Q, U}

0

0

1 0

1

1

1

0

Fig. 10.13