Re: trying to use the pumping lemma



TheGist wrote:
I want to show that L={0^{n^3+3n^2-2n} | n >=0} is not regular.
Here is my proof using the pumping lemma.
Is this correct? First, observe a few strings in L
0^0,0^2,0^48
Now, assume L is a regular language accepted by some DFA M of s states. Choose some a^s in L, where |a|>=s. Divide a into a=xyz=00^s0.
Coose x=0, z=0, and y=0^s. Now, for any way of dividing y into three parts uvw with v not equal to the empty string we already have a contradiction since for v=0 we have 0^3 which is not in L.


How does that look?

Not too good, but don't feel too bad since pumping lemma proofs
of non-regularity confuse a lot of people at first.

The pumping lemma says that if L is a regular language and w
is a string in L that is "long enough" (in your notation, w is
at least as long as s), then w may be written as w = xyz,
where

|y| > 0 (you've probably figured that |y| means the length of y)

|xy| <= s

and, for all i >= 0,

xy^{i}z is in L.

Your goal is to (1) assume L is regular, (2) find a w in L that's
long enough and (3) show that _no matter what x, y, and z are_
(satisfying the first two conditions above) there will be some
i for which xy^{i}z isn't in L (thus establishing the contradiction
you want).

A standard example is the language {0^{n^2} | n >= 0}. You should
be able to find a proof that this isn't regular in any of a
number of theory texts and adopt it to your example, but I'll get
you started.

Let w = 0^{s^3 + 3s^2 - 2s}. That's certainly in your L and since
s^3 + 3s^2 - 2s >= s (prove this), w will be "long enough." Thus, if
L were regular, the pumping lemma would apply to w.

Write w = xyz as above. You don't have the right to pick what x, y,
and z are, but you do know that 0 < |y| <= s (why?). You also know
that |w| = s^3 + 3s^2 - 2s so if we denote |xz| by t we'll have

s^3 + 3s^2 - 2s = t + |y|

Now we can try pumping w up. We see that

|xy^{2}z| = t + 2|y| = s^3 + 3s^2 - 2s + |y|

<= s^3 + 3s^2 - 2s + s (why?)

= s^3 + 3s^2 - s

Now, by the pumping lemma, xy^{2}z will be in L is L is regular,
but we can show that xy^{2}z can't be in L (Why? Convince yourself
that it lies strictly between two adjacent elements of L, in length
order).

[By the way, regular languages over a 1-symbol alphabet have a
particularly simple form. Roughly speaking, such a language
can't have length gaps that are too large. In particular, languages
like {0^{n!} | n >= 0} can't be regular.]

Hope this helps.


Regards,

Rick

.

Relevant Pages

  • 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)
  • Re: The pumping lemma
    ... That string is not in L, so we contradict the assumption that L ... >> chosen by Player 2 so that it represents some repetitive structure ... but that might be smaller than the n in the pumping lemma. ... that L is regular. ...
    (sci.math)
  • Re: pumping lemma (third try)
    ... Mark (The WannaBe) wrote: ... > comments and put my hands on a new wannabe trial using the pumping lemma on ... some string x followed by its reverse.} ... > I will assume that L is regular and therefore the pumping lemma ...
    (comp.theory)
  • Re: Pumping Lemma Palindrome
    ... Let n be the constant of the pumping lemma for L, ... ends in 10 is not regular? ... Is it safe to assume that since palindromes are not regular, ... Disregard previous advice. ...
    (comp.theory)
  • 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)