Problem Solving in Automata, Languages, and Complexity

50 FINITE AUTOMATA

Figure 2.31: Solution to Example 2.27.

and 6’ is defined by

w7’, 0) = {Qo, Ql) u { qi+l 1 qi E q’ and 1 < i 5 4)

ql?‘, 1) = blot u { qi+l 1 qi E q’ and 1 5 i 5 4).

This DFA Ik4’ has totally 32 states. We leave the transition diagram of S’ to
the reader. Cl

• Example 2.28 Consider the following multiplication table on {a, b, c}:

x a b c

acab

b b c a

c c b c

For any string w in {a, b, c} +, denote by value(w) the value obtained by mul-

tiplying symbols in w from left to right. For instance, let w = abcb. Then, we

value(w) = ((a x b) x c) x b = (a x c) x b = b x b = c, and

value(wR) = ((b x c) x b) x a = (a x b) x a = a x a = c.

Construct an NFA for the set L of all strings w over {a, b, c} such that
value( 20) = value(wR). (E.g., abcb E L and abb # L.)

Solution. Define Q = {qs, qa, qb, qc} and C = {a, b, c}. First, we define a
transition function S : Q x C + Q by 6(q,, z> = q2 for x E C, and s(Qx, y) = q2
ifzxy= x, for X, y, x E C; that is,

6 I a b c

Qs qa qb qc

4a 4c qa qb

qb !h !k qa

4c 4c qb !k

Clearly, for each x E C, the DFA I& = (Q, X,6, q9, {q2}) accepts the set of
all strings w over C having value(w) = X. We show Ma in Figure 2.32(a).