Problem Solving in Automata, Languages, and Complexity

84 FINITE AUTOMATA

any Ic > 0, zuvkw is in L. Take k = 0. We get xuw = O1OS+llOs+llOt, with
1 < - t <s. - Since t $ l(s + 1) (mod s + l), we get a contradiction. El

Note that, for any fixed integer p > 1, the language {0”10”10~ 1 n, m,p > -

l,qG nrn (modp)} is regular (see Exercise 3(f) of Section 2.3).

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

Recall, from Example 2.28, that for any string x in {a, b, c}+, value(x) denotes

the value obtained by multiplying symbols in x from left to right. Show that

the set

L = {xy 1 x, y E {a, b, c}*, 1x1 = 1~1, value(x) = value(y)}

is not regular.

Proof Assume, by way of contradiction, that language L is a regular set and

is accepted by a DFA M of s > 0 states. To find a contradiction, we select a

string a = bcS bc” E L and let x = b, y = cs and x = bc”. Apparently, a E L.

Now, we apply the pumping lemma to decompose y into 2/ = uvw with v # &

and XUV*WX C L. This means that, for any k > -1, bcS+klvlbcS E L; in

particular, bc sf21vlbcs E L. It follows that bcS+2~“~bcS = ,8r for some p and y

in {a, 6, c}’ with IpI = IyI and value(p) = value(y). From IpI = lyl, we know

that ,8 = bcs+lVl and y = cl”lbP. From the given multiplication table, we get

value(p) = b and value(y) E {a, c}. This is a contradiction. cl

* Example 2.65 Show that the set L of all strings over alphabet

that represent correct multiplication is not regular. For example, the relation

0 0 1 1

x 0 1 0 1

1 1 1 1

implies that the following string is in L:

(9)(I)(1)(1)*