Results 1 to 2 of 2

Math Help - Pumping Lemma

  1. #1
    Newbie
    Joined
    Sep 2012
    From
    Puerto Rico
    Posts
    6

    Pumping Lemma

    Hello i am trying to do this exercise of the pumping lemma and i have no idea how to do it need help please.
    The exersice is the following:

    Use the pumping lemma to prove that the following language is not regular.

    L{a^kb^n : k>=2n, and k,n>=0}

    Thanks in advance
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718

    Re: Pumping Lemma

    In this case, one has not to add extra characters (since adding extra a's produces strings still in the language), but remove a nonempty substring of a's. Recall that the pumping lemma says that a sufficiently long string w can be written as w = xyz so that |y| >= 1 and xyiz is in the language for all natural numbers i including 0.

    If you need more hints, see here (PPT) or p. 5 here (PDF).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Pumping Lemma
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: October 25th 2010, 08:52 AM
  2. Pumping Lemma
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: May 7th 2010, 12:46 AM
  3. Pumping Lemma proof...
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: March 15th 2010, 07:50 AM
  4. Discrete Finite Automaton and the pumping lemma
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: September 24th 2009, 04:39 AM
  5. Pumping Lemma
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 28th 2009, 12:41 PM

Search Tags


/mathhelpforum @mathhelpforum