# How do I use the pumping lemma for a^n b^m a^(n+m) ? How can I choose the pumping length?

$$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=a^nb^ma^{n+m}$$

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

w=xy^iz

Now we set i = 0

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

$$\implies$$ L is not regular.

• 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 – lox Aug 9 '20 at 23:18
• 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? – Rapiz Aug 9 '20 at 23:40
• 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 – lox Aug 10 '20 at 0:42
• So how would this done correct? – Rapiz Aug 10 '20 at 14:51
• 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 – 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.

Cheers.

• thank god I've passed the exam haha – Rapiz Jan 18 at 20:41
• @Rapiz congratulations :) – 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$$.