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

Question

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

Answer 1

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.

Answer 2

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