0
$\begingroup$

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.

$\endgroup$

2 Answers 2

1
$\begingroup$

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.$$

$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$
    – Dhruv
    Commented May 20 at 10:39
  • $\begingroup$ @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. $\endgroup$
    – Knogger
    Commented May 20 at 11:50
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.