1
$\begingroup$

Recently I stumbled across this language $L=\{a^{n}a^{{(n + 1)}^2-n^2} \in \Sigma^* \mid n\geq 0\}$ that I can rewrite as $a^{3n + 1}$.

So I applied the pumping lemma to see if it is non regular, and I get:

  • given a pumping length p I should have a string $z\in L$ such that $\mid z \mid \ge p$
  • I choose $z=a^pa^pa^pa$ such that $z\in L$ and $\mid z \mid = (3p + 1)\ge p$
  • now I can slipt the string in 3 parts, $z=uvw$ with $u=a^{p-1}, v=a,w=a^{2p}a$ and it satisfies the two following conditions of the lemma $\mid uv \mid \leq p$ and $\mid v \mid > 0$
  • then given $z = uv^iw$, if I pump $v$ I see that $z \notin L$ because if for example I choose $i=2$ than $\mid z \mid = (p-1)+i+2p+1=3p+2 \geq 3p+1$

So $z \notin L$ and it means that $L$ is not regular, but I noticed that I can construct a DFA that accepts this language:

dfa

So now I'm really confused. Probably I'm applying the pumping lemma in the wrong way but I don't understand where.

UPDATE

Now, thanks to all of you, I think I understood my mistake. So to prove that a language is not regular I have to show that every decomposition fails to satisfy the pumping condition for some pumping number $i$. But in this case there is a decomposition that satisfies the pumping condition so I can't prove that the language is regular (but we know it is regular because we can construct a DFA that accepts it).

Improve this question
$\endgroup$
3
  • $\begingroup$ This is a classic mixup. The pumping lemma states that there exists a decomposition of long enough words $w\in L$ to $w=xyz$ such that $xy^iz\in L$ for all $i$. In your case, choosing $y=aaa$ works, the pumping lemma does not state that every decomposition works. $\endgroup$
    – Ariel
    Jun 3, 2018 at 12:38
  • $\begingroup$ Ok, but now I'm confused on how to decompose the string. If I want to prove that a language is not regular, shoudn't I choose a decomposition that belongs to the language and pump it with an arbitrary $i$ such that the pumped string doesn't belong anymore to the language? $\endgroup$
    – tokenizer
    Jun 3, 2018 at 13:06
  • $\begingroup$ No you have to show that every decomposition fails to satisfy the the pumping condition for some pumping number $i$ if you want to show that a language is not regular. $\endgroup$
    – ttnick
    Jun 3, 2018 at 13:43

1 Answer 1

Reset to default
0
$\begingroup$

You should notice that if the conditions hold, the language can be regular (necessary, but not sufficient). However, you proved the third condition is not held in your case, hence it is not regular which this is not true. Therefore, your proof is not correct.

On the other hand, if we suppose $x = a$ and $y = a^{3}$ and $z = 3n-4$ we can say $xy^nz$ is in $L$ for all $n\geq1$ ($p = 4$). Hence, we can't proof $L$ is not regular by pumping lemma.

Improve this answer
$\endgroup$
4
  • $\begingroup$ This is not true for every language. The pumping lemma is only a necessary condition for regularity. There are languages where all conditions are satisfied but are not regular. $\endgroup$
    – ttnick
    Jun 3, 2018 at 13:45
  • $\begingroup$ @PHPNick Yes. I've corrected it to "can be regular". $\endgroup$
    – OmG
    Jun 3, 2018 at 13:46
  • 1
    $\begingroup$ But with your decomposition $\mid xy \mid \nleq p$ $\endgroup$
    – tokenizer
    Jun 3, 2018 at 14:56
  • $\begingroup$ @tokenizer it is corrected. there exists a $p$ such that ... $\endgroup$
    – OmG
    Jun 3, 2018 at 15:05

Your Answer

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

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