Pumping Lemma proof...

• Mar 15th 2010, 06:08 AM
alireza6485
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.

• Mar 15th 2010, 07:38 AM
emakarov
Quote:

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}\}$?
• Mar 15th 2010, 07:42 AM
alireza6485
well a*b* is considered for regular so it gets to contradiction.
• Mar 15th 2010, 07:46 AM
emakarov
Quote:

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.
• Mar 15th 2010, 07:50 AM
emakarov
Quote:

well a*b* is considered for regular so it gets to contradiction.
What is the definition of L?