Pumping Lemma,regular languages

Question

Lets say that we have the language L = { $a^n$$b^m$$c^{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.

Answer 1

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

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