# Pumping Lemma,regular languages

Lets say that we have the language L = { $$a^nb^mc^{m+n}$$ $$|$$ $$m$$,$$n$$ $$>=0$$ } What is the way that i should follow to prove

that the language is not regular?

• Assume that the language is regular.
• So,there is a string $$w\in L$$ such that $$w = xyz$$ , $$|xy|\leq n, y\neqε$$, n is the pumping length

Lets say that the string that i choose( w string) is $$w = a^nb^mc^{m+n}$$

Is this choice correct ? Can someone explain me the best choice of $$y$$ ?

Should be $$y = a^{n-r}$$ and $$x = a^n$$ ? Because of $$|xy|\leq n$$ ?

Thank you and sorry for my english.

Pumping Lemma for regular languages (by Wikipedia):
Let $$\displaystyle L$$ be a regular language. Then there exists an integer $$\displaystyle p\geq 1$$ depending only on $$\displaystyle$$ such that every string $$\displaystyle w$$ in $$\displaystyle L$$ of length at least $$\displaystyle p$$ ($$\displaystyle p$$ is called the "pumping length") can be written as $$\displaystyle w=xyz$$ (i.e., $$\displaystyle w$$ can be divided into three substrings), satisfying the following conditions:

1. $$\displaystyle |y|\geq 1$$
2. $$\displaystyle |xy|\leq p$$
3. $$\displaystyle (\forall k\geq 0)(xy^{k}z\in L)$$

The given Language is $$L = \{a^nb^mc^{n+m}|m,n\geq 0\}$$. We want to show that L is not regular through proof by contradiction using the pumping lemma.
First we assume that $$L$$ is regular as you wrote. This implies the existence of the pumping length $$p$$. You called the pumping length $$n$$ which might lead to confusion cause $$n$$ appears in the definition of the language; so I called it $$p$$. Since we make a proof by contradiction we need to choose a word $$|w| \geq p, w\in L$$ and show for every possible partition into $$w = xyz, |xy|\leq p, |y|\geq 1$$ that there is a $$k$$ such that $$xy^kz\notin L$$.
Now what $$w$$ could you choose? I think $$a^pb^pc^{2p}$$ is a good choice. Because $$w = xyz = a^pb^pc^{2p}, |xy|\leq p, |y| \geq 1$$ implies that $$x = a^{i}, y = a^j, i+j \leq p, j\geq1$$ thus $$xy^pz \notin L$$ because the the string would look like $$a^{i+p\cdot j}b^pc^{2\cdot p}$$ and $$i+p\cdot j + p \neq 2p$$, so the property of the language is violated. That's how proof using the pumping lemma usually looks like.
• So, you choose the word $a^pb^pc^2p$ because the sum of the powers of a,b must be on the power of c. After this, cause of $|xy| < p$ , x and y must contain only a's and not b's or c's So the $z$ part of the word is something like -> $z = a^{p -i -j}b^pc^{2p}$ ? – TuMama Jul 7 '20 at 13:06
• yes exactly. the word $w$ you choose must be in the language $w\in L$. and your equation for $z$ is right. – plshelp Jul 7 '20 at 13:14
• This works, but a trifle easier is to pump $a^pc^p$. – Rick Decker Jul 7 '20 at 18:40