Results 1 to 5 of 5

Math Help - Pumping Lemma proof...

  1. #1
    Newbie
    Joined
    Mar 2010
    Posts
    6

    Pumping Lemma proof...

    Hello,
    Could you please let me know what is wrong with the following proof:
    proof that L = a*b* is not regular:Suppose L is regular, so the Pumping Lemma applies to L. Let p be the pumping constant for L.Consider w = a b^p ∈ L.
    | w | ≥ p, so the pumping lemma applies to w.
    Thus there exist x, y, z ∈ { a, b }* such that w = xyz and 1 ≤ | y | ≤ p.
    Take y = abn (n ≤ p), so x = ε and z = bp-n.
    Now w2 = x y^2 z = a b^n a b^p ∉ L.
    This contradicts the Pumping Lemma and so L is not regular.

    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,527
    Thanks
    773
    L = a*b* is not regular
    Before reading the proof: how is it not regular if you define L by a regular expression? Did you mean L=\{a^nb^n\mid n\in\mathbb{N}\}?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Mar 2010
    Posts
    6
    well a*b* is considered for regular so it gets to contradiction.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,527
    Thanks
    773
    Take y = abn (n ≤ p), so x = ε and z = bp-n.
    This is not clear. You don't have control over x, y, and z: they are determined by the (proof of the) Pumping Lemma. One you fixed w, you are given x, y and z that satisfy the properties stated in the lemma.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,527
    Thanks
    773
    well a*b* is considered for regular so it gets to contradiction.
    What is the definition of L?
    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. Discrete Finite Automaton and the pumping lemma
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: September 24th 2009, 04:39 AM
  4. Proof of a lemma
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: April 29th 2009, 05:19 AM
  5. Pumping Lemma
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 28th 2009, 12:41 PM

Search Tags


/mathhelpforum @mathhelpforum