pumping lemma (second try)

From: Mark \(The WannaBe\) (mark_hsn_at_hotmail.com)
Date: 10/13/04 

Date: Wed, 13 Oct 2004 22:07:42 +0200

Hi

I am a wannabe of computer science and I am trying my best on a prove
applying the pumping lemma.

It is a problem from "Introduction to Automata Theory, Languages, and
Computation" by Hopcroft et al.
It is the problem 4.1.1.f. I got help on 4.1.1.c in sci.math, but I was told
that this news group was more appropriate for these kinds of questions.

I want to know if this is a correct application of the pumping lemma. My
trial is between the lines --*--*--.

--*--*--
The problem is: Prove that L={0^n1^(2n)|n>=1} is not a regular language.

I will prove it by use of the pumping lemma. We will assume the language L
is regular and then show that this assumption leads to a contradiction. If L
is regular then we can apply the pumping lemma to repetitively pump up a
substring of a string w belonging to L and still get new strings also
belonging to L. The pumping lemma is applied as follows.
We chose strings from L of at least length p where p>=1, we chose the string
w=0^p1^(2p).
It is obvious that |w|>=p. Now we most have that |xy|<=p for that to be true
then we have that xy = 0^p.
If r + s = p and s>0 then we chose x = 0^r = 0^(p-s) and y=0^s and z =
1^(2p). Now chose k=0 then we have that xz = 0^(p-s)1^(2p) which does not
belongs to L and we therefore have a contradiction and our assumption was
wrong, L is not regular.
--*--*--

I have tried to learn from postings at sci.math. Is the above application
and presentation of a prove using the pumping lemma correct? Should I
explain the pumping lemma before using it, or is it appropriate just to
mention the pumping lemma an then assume that the meaning of w=xyz, |xy|<=n,
y =/=epsilon, etc. is well known?

Kind regards
Mark (The WannaBe)

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)
    ... >> 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: 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: 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: How to prove "Cfls are not closed under shuffling"
    ... "If a language L is infinite and ... string w in L with length>= p can be ... Let p be the integer guaranteed by the Pumping Lemma. ... any theorems of the form "If L is context-free, ...
    (sci.math)