Re: The pumping lemma

From: Rick Decker (rdecker_at_hamilton.edu)
Date: 10/13/04 

Date: Wed, 13 Oct 2004 10:27:42 -0400

Rick Decker wrote:
>
>
> Mark (The WannaBe) wrote:
>
>> Hi, I am loosing my head on the solution to this problem from
>> "Introduction to Automata Theory, Languages, and Computation" by
>> Hopcroft et al. It is exercise 4.1.1.c. I believe I can come with a
>> solution but I do not understand the solution given by the book here
>> http://www-db.stanford.edu/~ullman/ialcsols/sol4.html.
>>
>> If I apply the pumping lemma game then I would go
>>
>> 1) Player 1 chose L = {0^n10^n}
>> 2) Player 2 chose n=3 (not the n in L but the n of the pumping lemma rule
>> 3) Player 1 chose w = 010 (the length of w is less than or equal to 3
>> as required)
>> 4) Player 2 chose x = epsilon, y = 0, z = 10
>> 5) Player 1 picks k=2, then we get the string 0010, which does not
>> belong to L
>>
>> But the book's solution says the following
>> --------
>> Let n be the pumping-lemma constant (note this n is unrelated to the n
>> that is a local variable in the definition of the language L). Pick w
>> = 0^n10^n. Then when we write w = xyz, we know that |xy| <= n, and
>> therefore y consists of only 0's. Thus, xz, which must be in L if L is
>> regular, consists of fewer than n 0's, followed by a 1 and exactly n
>> 0's. That string is not in L, so we contradict the assumption that L
>> is regular.
>> --------
>>
>> I cannot see how the solution of the book can say that because |xy| <=
>> n then y consists of only 0's ??? I could have chosen x = epsilon, y =
>> 01 and z = 0, couldn't I (?), because |yz|<3, and then, y, would not
>> be consisting of only 0's? Is it because that, y, should always be
>> chosen by Player 2 so that it represents some repetitive structure
>> already existing in L? I cannot see the book is making this constraint
>> or is this constraint implicit in that Player 2 tries to prohibit
>> Player 1 in succeeding and if Player 2 were choosing y=01 he would
>> make it to easy for Player 1 to succeed?
>>
>>

I know that some people teach this kind of adversary argument (as it's
known) using the "player 1/player 2" form, but I've found that it
tends to confuse more students than it helps. Robin has already pointed
out the problem with your argument--you are picking a specific value
(3) for n, but that might be smaller than the n in the pumping lemma.

Let me go through the strategy pretending to be a student. See if this
helps you understand how to approach these proofs.

We wish to show L = {0^n10^n | n >= 0} isn't regular. First, assume
that L is regular. Then, if we can argue to a false result, we'll
have no choice but to realize our assumption was wrong, thus showing
that L is not regular.

Since L was assumed to be regular, the Pumping Lemma applies. Thus
there is an integer p > 0 such that (restating the PL) if w is any
string in L of length >= p, we can decompose w as xyz, where the
length of xy is less than or equal to p, y is not empty, and
x(y^i)z is in L for all i = 0, 1, 2, ... .

Now comes the hard part. We need to pick a string w in L to pump.
We're looking for a string that

1. Is in L,
2. Has length at least p and
3. Can be pumped up or down to produce a string not in L

Picking the string is more of an art than a science--you get
better with practice, but there's no algorithm to help you.
Genarally, the string will be defined in terms of the
unspecified p of the PL.

Let's try the string w = 0^p10^p. That's certainly longer than
p so we can use the Pumping Lemma on it.

Write w = 0...010...0, with p zeros before the 1 and p zeros
after. Now, where will the pumped part, y, live? Well, since
xy is the left part of the string and xy has length <= p
it must live among the first group of zeros, so y must
live in the first collection of zeros.

Now form the pumped string u = xz (pumping y down). We've
removed some 0s from the left when we took y out, so
the string u has fewer 0s on the left than it does on
the right, and hence it can't be in L. However the PL
says that it must be in L, so we have a contradiction,
thus we must have been wrong in assuming L was regular.
Done.

Hope this helps,

Rick

Relevant Pages

  • Re: pumping lemma for CFL
    ... The "basic" version of the pumping lemma goes more or less like this: ... resulting string is in L. ... For example, given some string in a language L divided into three parts x, ... If L is regular, then all these strings have to be in L given that xyz is ...
    (sci.math)
  • Re: pumping lemma (third try)
    ... >> you a string not in L. ... >> contradiction and the proof that L isn't regular breaks down. ... > and answering my wannabe trials and questions. ... > there are no adjacent equal substrings. ...
    (comp.theory)
  • Re: pumping lemma (third try)
    ... some string x followed by its reverse.} ... > I will assume that L is regular and therefore the pumping lemma ... > Now I will divide the PL string w into the PL substrings x, ...
    (comp.theory)
  • Re: trying to use the pumping lemma
    ... Here is my proof using the pumping lemma. ... assume L is a regular language accepted by some DFA M of s states. ... is a string in L that is "long enough" (in your notation, ...
    (comp.theory)
  • Re: pumping lemma (third try)
    ... >> Duncan's comments and put my hands on a new wannabe trial using the ... >> pumping lemma on the problem below. ... I can decompose a string w belonging to L into x, ... >> being regular without that PL applies, ...
    (comp.theory)
Loading