Problem Solving in Automata, Languages, and Complexity

2.7 Minimum Deterministic Finite Automata 75

shows that, although NFA’s and DFA’s have the same computational power for

recognizing languages, they are different in term of computational complexity.

In general, finding the equivalence classes of RL for a given language L

(from its regular expression or an informal description) may not be easy.

However, if we are given a DFA M for L, then there is a simple method to

find the equivalent minimum DFA.

The basic idea of this method is the simple observation of Lemma 2.47: For

any DFA M, two input strings which end at the same state of M must belong

to the same equivalence class of RL. That is, for any DFA M = (Q, C, 6, s, F)

accepting L, if we define, for each 4 E Q, Sq = {Z E C* 1 S(S,X) = q}, then

every S, is contained in a single equivalence class of RL. Thus, we may define

a new equivalence relation R;J on Q as follows:

p R;14 a Sp and Sq are in the same equivalence class of RL

• (VW) [QP, w> E F (6(a, w) E F].
  Each equivalence class of RL corresponds to an equivalence class of RL in the
  following way:

From this relation, we can build the minimum DFA M* = (Q*, C, 6*, Sf, F*)

for L as follows:

(1) Q* = ([Qlq, I q E Qh

(2) &*([!f]R;,a) = [&,a)]R2;

(3)

*- - [SIR;;

(4) "F = ([fR; 1 f E F)-
Thus, to construct the minimum DFA M which is equivalent to a given
DFA M, all we need to do is to compute the equivalence classes of RE. We
demonstrate three different methods in the next example.

Example 2.53 Find the minimum DFA equivalent to the DFA M of Figure

2.47.

Solution 1. Let M = (Q, W, go> F), whue Q = {go, 41,. l. , Qs}, and let

L= L(M). We note that states qi and qj are equivalent under RL if and

only if for all strings w, S(q;, w) and S(qj, w) both are in F or both are not in

F. Therefore, to find the relation RL between any two states, we construct

a graph G as follows: Each vertex is an unordered pair (qi, qj) of states. Let

U be the set of vertices (qi, qj) with one vertex qi E F and the other vertex

qj 4 F. For each vertex (qi, qj) $ U, with i # j, we draw edges

for all a E C. Then, it is clear that qi I?; qj if and only if there is no path in

G from (q;, qj) to a vertex in U.