Results 1 to 4 of 4

Math Help - Pumping Lemma

  1. #1
    Junior Member
    Joined
    May 2010
    Posts
    26

    Pumping Lemma

    Hey guys,

    Came accross this question today and would greatly appreciate any assistance with it.

    Use the Pumping Lemma to prove that language
    L
    = {0^n1^m : n > m}

    is not regular

    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,551
    Thanks
    783
    This seems a little tricky. If we try using the simple formulation of Pumping Lemma, then the "pumping segment" may consists of 0's. Multiplying this segment won't lead us to a word that is not in the language.

    However, the General version of pumping lemma for regular languages states that a "pumping segment" can be found in every sufficiently long subword. Let's take the number p given by the lemma and consider 0^{p+1}1^p (in terms of the theorem, u=0^{p+1}, w=1^p and v=\epsilon). Then it should be possible to find a nonempty fragment of w that can be iterated, and this would lead us out of the language.

    Another way is to use intersection and complement properties of regular languages to reduce the problem to showing that 0^n1^n is not regular, where the simple version of the lemma works.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    May 2010
    Posts
    26
    Thankyou emakarov. Your help has been great.

    Is your reponse a sufficient enough answer??
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,551
    Thanks
    783
    Thankyou emakarov. Your help has been great.
    You are welcome.

    Is your reponse a sufficient enough answer??
    If I understand it right, in this forum people provide ideas that may be helpful, but only you can decide whether you are convinced by them and whether you can convince others (your instructor).
    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 proof...
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: March 15th 2010, 07:50 AM
  3. Discrete Finite Automaton and the pumping lemma
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: September 24th 2009, 04:39 AM
  4. work by pumping
    Posted in the Calculus Forum
    Replies: 8
    Last Post: August 19th 2009, 02:09 PM
  5. Pumping Lemma
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 28th 2009, 12:41 PM

Search Tags


/mathhelpforum @mathhelpforum