Problem Solving in Automata, Languages, and Complexity

70 FINITE AUTOMATA

2n2 + 2 states. If we convert this NFA to an equivalent DFA, the new DFA
would have, in the worst case, 20cn2) states.
Whereas this large size of DFA’s is unavoidable in some cases, many DFA’s
constructed this way can be reduced to smaller, equivalent DFA’s. In this
section, we show how to find, for a given regular language, a DFA with the
minimum number of states. Such a DFA is called a minimum DFA.
To begin with, we define, for any language L C C, - a relation RL on C as
follows:
xR~y ifandonlyif (‘dw)[xw~L~yw~L].
This relation RL is an equivalence relation. That is, it satisfies the following
properties:
(1) Reflexivity: (Vx E C) [x RL x];
(2) Symmetry: (Vx, y E C) [x RL y 3 y RL x];
(3) Transitivity: (‘dx, y, x E C”) [x RL y, y RL x 3 x RL z].
Recall that for any equivalence relation R on a set S and for any x E S,
the class
[$I = {Y E s I XRY)
is called an equivalence class containing x. Every equivalence relation R on a
set S divides S into disjoint equivalence classes. The number of equivalence
classes is called the index of R, and is denoted by Index(R).

Example 2.45 Let L = {x E (0 + 1)’ 1 Ix 1 is odd}. Find all equivalence

classes of RL.

SoZution. Note that xR~y if and only if 1x1 - lyl is even. Therefore, there are

two equivalence classes

[& = {x E (0 + l)* I 1x1 is even}

PI RL = {x E (0 + l)* ( 1x1 is odd}.^0

Example 2.46 Let L be the set of nonempty b inary strings starting and end-

ing with the sum e symbol. Find all equivalence classes of RL.

SoZution. We first show that xR~y if and only if x and y start with the same

symbol and end with the same symbol.

For the forward direction, we first assume that x and y start with different

symbols; for instance, x starts with 0 and y starts with 1. Then, x0 E L and

y0 $ L. This implies that x and y do not satisfy the relation x RL y. Or,

equivalently, x RL y implies that x and y start with the same symbol. Next,

note that x RL y implies that x E L ( y E L. Since x and y start with the

same symbol, they must end with the same symbol.

For the backward direction, we assume that x and y start with the same

symbol and end with the same symbol. Since x and y start with the same