# Help regarding a proof in which i am able to prove a regular language $(a(a+b)*)$ as irregular using pumping lemma

I have a regular language $$a(a+b)^*$$ to which i applied pumping lemma.

Let the pumping length be $$'p'$$

and the example string be $$w=a(a+b)^{p-1}$$.
The string satisfies the condition that it is at least length 'p'.

We now divide it into 3 parts $$x y z$$ with $$x=epsilon ,y= a(a+b)^{p-1} , z= epsilon$$.

This division also satisfies the condition that $$|xy|<=p \land |y|\neq epsilon$$.

Thus, $$w=xy^1z$$.
since , i can be zero in $$y^i$$, we pump down to get,

$$w=xy^0z = epsilon$$
which doesn't belong in the given language $$a(a+b)^*$$.

Thus,now that we have proved that $$\exists w\in a(a+b)^*$$ such that it can't be pumped.

I have already spent 2 hours trying to figure out what is wrong with this proof as the results doesn't make sense. Any help is appreciated.

## 2 Answers

This isn't how the Pumping Lemma works. The Lemma states that "if $$L$$ is regular then for all $$w \in L$$ there exists factors $$w = xyz$$ satisfying ...", not "if $$L$$ is regular then for all $$w \in L$$ all factors $$w = xyz$$ satisfy ...". So just because you found one factorization of $$w$$ that can't be pumped doesn't mean that there is none.

There is a factorisation of $$w$$ that can be pumped, e.g.

$$x = a, y = (a + b)^{p - 1}, \text{ and } z = \varepsilon.$$

• Thanks. I understand your point . You mean that every string (length>p) belonging to a regular language needs to have a pumpable part and NOT that every part of that string needs to be pumpable, right? But if this is so, can you comment on the language $E={0^i1^j|i>j}$? It can be showed to be irregular only by the case $0^{p+1}1^p$ . in this case y is all zeroes . It is pumpable for i>=1 in $y^i$ . But for i=0 , the resulting string doesn't belong to w. The only thing i can think of is that pumping lemma is not enough to prove irregularity of this language E.Thanks in advance Commented May 20 at 10:39
• @Dhruv Yes, the PL is only an if-then statement (not iff as I originally wrote 🤦). The Lemma only states that if a language is regular, it has this property. But there are examples of non-regular languages satisfying the PL, for an example see here. I don't really see a problem in the example you gave, since you showed that one string can't be pumped, it follows from the PL that $E$ is not regular. Commented May 20 at 11:50

Every regular expression have an automata recognising it and the same holds for the converse too. Link to a previous post. Regular languages are defined as the language that can be recognized by a deterministic automaton.Thus every regular expression fall under the class of regular languages.