Problem Solving in Automata, Languages, and Complexity

2.8 Pumping Lemmas 85

Proof. Assume, by way of contradiction, that L is regular and is accepted by
a DFA M of s > 0 states. Consider the following string a:

(P)‘(i)($

The string CY represents the multiplication of the following form:

and hence is in L. We let

q FgS( i), y=( gs, x=E.

By the pumping lemma, ZJ can be written as y = uzlw such that v # E and

XXHUX E L. This implies the following incorrect multiplication:

Thus, we have reached a contradiction.^0

• Example 2.66 Show that the set L2 of the binary expansions of the integers
  in set A = {an 1 n > - 1) is regulur, but the set L3 of the ternary expansiotis
  (base 3 representations) of the integers in A is not regular.

Proof. It is clear that the set L2 consists of all strings of the form 10” for all

n > 1; that is, L2 = lo+. Thus, L2 is regular.

Next, we assume, for the sake of contradiction, that La is regular and is

accepted by a DFA A4 of s > 0 states. For any string t E (0, 1,2}*, we let nt

be the integer whose ternary expansion is t (with possible leading zeros). We

select an arbitrary x in L3 with 1x1 - > s. We apply the first pumping lemma

(Lemma 2.57) to the string IX: to get z = UVW, with v # E and UV*W E L3.

Then, for any k > - 0, the string avkw E L3; that is, nuvkw E A. Let 2”” be

the integer whose ternary expansion is equal to z&w. Since v # E and since

z > 0, we know that nzh+l > mk: for all k 2 0. What is 2”k in terms of nU, n,

and n,? Assume that Iv1 = p > 0 and (WI = 4. Then, for k > - 1, we have

2 mk = n,. skP+q + nv(3(k-1)P+4 + 3(kv2)P+Q +... + 34) + nwe

It follows that, for k > - 2,

2 mk -2 mk-1 = n, - 3’P+Q + (n, - n,). 3CkB1>P+4

• 
  
  
  
  • 3(k-1)P+q(n,(3p - 1) + n,).