Problem Solving in Automata, Languages, and Complexity

86 FIN1T.E AUTOMATA

Since 3(lc-l)P+P is an odd integer, and since 2”k-1 divides 2”” - 2”“-‘, we

must have that 2mk-1 divides the integer n, (3P - 1) +n,. However, this cannot
be true for Ic > - 3, since

n,(3p-1)$n,<n,-3p+q$nv~3q+nW=2m1 - <2”“.

So, we have reached a contradiction. Cl

Sometimes, using the pumping lemma directly to prove a language non-

regular takes some thinking to come up with the required string a. In these

cases, we can often combine the pumping lemma with the closure properties

of Section 2.6 to produce simpler proofs. The following are some examples.

Let #&.Q denote the number of occurrences of symbol a in string w.

Example 2.67 Show that L = {W E {O,l}* 1 #o(w) # #l(w)} is not regular.

Proof. We may prove this by selecting CY = O”l@!)+“, with IX: = &, y = OS and

X= l@!)+‘, and arguing that for any way of dividing y into y = uvw with

v # E, XUVkWX = O”+(k-l)lVll(“),+” 4 L when k = (s!)/lvl + 1. (Note: Since

I4 < IYI = s, k must be an integer.)

This proof, though somewhat inspiring, is not easy to find. A simpler proof

is as follows:

(1) L1 = {OYn I n > 0) is not regular. (This can be proved by the pumping

lemma easily as% Example 2.60.)

(2) L2 = (20 E {O,l} 1 #o(w) = #l(w)} is not regular, since l&01* = L1

is not regular. (If L2 were regular then, by the property that regular

languages are closed under intersection, L1 would be regular.)

(3) L is not regular since L = L2 is not regular.^0

Example 2.68 Show that L = {a n b mck ~n,m,k>O,n#morm#kork# -

n} is not regular.

Proof. It is easy to use the pumping lemma to prove that

znubc* = {unbncn 1 n > - 0)

is not regular.

not regular.

Thus, by the closure properties of the regular languages, L is

q

Example 2.69 Let L be a regular language. Show that

L’ = {xx I (3~) [lx/ = (y( = Iz( und xyx E L]}

is not necessarily regular.

Proof. Consider the regular language L = u* bc*. For an arbitrary string u’bc-l

in L with i + j + 1 = 3n, let uibd = xyx with 1x1 = 1~1 = 1x1 = n > 0. There

are three cases: