Results 1 to 5 of 5
Like Tree1Thanks
  • 1 Post By SlipEternal

Math Help - pumping lemma

  1. #1
    Junior Member
    Joined
    Sep 2013
    From
    Toronto
    Posts
    28

    pumping lemma

    Hi
    I am trying to prove if language is not regular. my language is {a^i b^j c^l | where i=j}.
    I assume this language is regular and that there exist constant p
    I am trying to pick my string w but i don't know what are constrains on l.

    So if i pick my string on at least p length it will be w = a^p b^p c^?

    Do I have to consider 3 cases such as :

    w = a^p b^p c^(l<p)
    w = a^p b^p c^(l>p)
    w = a^p b^p c^(l=p)

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,759
    Thanks
    680

    Re: pumping lemma

    Don't set l at all. Let w = a^pb^pc^l for some choice of l. Now, suppose there is some decomposition w = xyz with |xy|\le p, |y|\ge 1. Hence, y must consist only of a's, and it must have at least one. Now pump up y.
    Thanks from emakarov
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Sep 2013
    From
    Toronto
    Posts
    28

    Re: pumping lemma

    hi thanks so much. It looks like i can do few things:

    I can say w0 = xy^0z = xz (this actually drops y out) and therefore we have at least 1 less 'a' than b
    I can say w2 = xy^2z = which adds at least 1 'a' and makes it more 'a' than 'b'
    ....
    ....
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,759
    Thanks
    680

    Re: pumping lemma

    exactly
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Sep 2013
    From
    Toronto
    Posts
    28

    Re: pumping lemma

    thank you for input
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Pumping Lemma Problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 1st 2013, 09:59 AM
  2. Pumping Lemma
    Posted in the Advanced Math Topics Forum
    Replies: 1
    Last Post: September 23rd 2012, 01:26 PM
  3. Pumping Lemma
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: October 25th 2010, 08:52 AM
  4. Pumping Lemma
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: May 7th 2010, 12:46 AM
  5. Pumping Lemma
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 28th 2009, 12:41 PM

Search Tags


/mathhelpforum @mathhelpforum