$L = {a^n + b^m + a^{n+m}}$

This is the language I want to show is not regular.

Now my problem is to choose p correctly.

Can I just set it as p=2*(n+m) ?

That's the problem I am facing now.

Thanks for any help I am starting to learn it to use the pumping lemma.

Edit: In the meantime I have done this:


|w|= 2(n+m)=p

$|xy|\leq 2n + 2m$

We choose $x=a^n, y=b^m, z=a^{n+m}$

$|a^nb^m|=nm \leq 2n+2m$


Now we set i = 0

$w_0=a^na^{n+m} \notin L $

$\implies $ L is not regular.

  • 1
    $\begingroup$ You can't "set" the pumping length. You can set the string (while making sure its length $\geq p$, and show that it cannot be pumped $\endgroup$ – lox Aug 9 '20 at 23:18
  • $\begingroup$ Thanks is my try correct? As I know now I have only to provide that the length of xy is smaller than the overall word length. Yes? $\endgroup$ – Rapiz Aug 9 '20 at 23:40
  • $\begingroup$ No. You can't choose $x,y,z$. The lemma states any word $w$ of sufficient length can be written as $w=xyz$. You need to choose such $w$ so that for every distribution of $xyz$ cannot be pumped $\endgroup$ – lox Aug 10 '20 at 0:42
  • $\begingroup$ So how would this done correct? $\endgroup$ – Rapiz Aug 10 '20 at 14:51
  • $\begingroup$ how about setting m and n = p/2? So if we pump xy it is not longer in the language ? Is this legit? With this any distribution will not longer be in the language if xy is pumped $\endgroup$ – Rapiz Aug 10 '20 at 22:44

It seems that you are trying to force the string length to be $p$, which is not necessary. What is required is that $|xy| \leq p$. The length of $w$ can be greater than $p$. Also, $n$ or $m$ can be $p$ or some multiple of $p$, whatever makes the reasoning for the impossibilty of partition of $w$ to satisfy the lemma. With that, I think you can follow through and complete your proof.

Just remember, the aim is not to look for a partition of $w$ that does not work. Rather show that no partition works.


  • $\begingroup$ thank god I've passed the exam haha $\endgroup$ – Rapiz Jan 18 at 20:41
  • $\begingroup$ @Rapiz congratulations :) $\endgroup$ – Russel Jan 19 at 11:24

You can't "set" the pumping length.

The pumping lemma states that if $L$ is a regular language, then there is a constant $N > 0$ such that if $\sigma \in L$ and $\lvert \sigma \rvert \ge N$ then there is a division $\sigma = \alpha \beta \gamma$ with $\lvert \alpha \beta \rvert \le N$, $\beta \ne \varepsilon$ so that for all $k \ge 0$ the string $ \alpha \beta^k \gamma \in L$

Here $N$ is the "pumping length".

The use you want to give the pumping lemma is to show it doesn't apply to your language, so the language isn't regular. I.e., no $N$ works.

General schema is typical proof by contradiction.

Assume $L$ is regular, thus the pumping lemma applies. Let $N$ be the [anything at all, we want to prove none works] constant of the lemma. Select $\sigma \in L$ [as the lemma states all long enough strings work, you are free to select a easy one to work with]. Now prove no division $\alpha \beta \gamma$ of $\sigma$ works by picking a "nice" $k$ and prove $\alpha \beta^k \gamma \notin L$.

In your case: Easy to work with is $\sigma = a^N b c^{N + 1}$, any division will give $\alpha \beta$ only $a$, repeating $\beta$ say twice ($k = 2$) will give too many $a$ for the (fixed) number of $c$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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