# Pumping Lemma for Regular Languages with 3 variables (a^nb^mc^m)

I've been trying to understand the pumping lemma, and how to apply it to a language such as a^nb^mc^m where n >= 0 and m >= 0. The pumping lemma states that:

For any regular language L, there exists an integer n, such that for all x ∈ L with |x| ≥ n, there exists u, v, w ∈ Σ∗, such that x = uvw, and

(1) |uv| ≤ n

(2) |v| ≥ 1

(3) for all i ≥ 0: uviw ∈ L

It states that there exists some n such that this holds true. In the language a^nb^mc^m if I were to replace m with the pumping length, and choose a pumping length, for example 3, such that a^nb^pc^p I could get the string:

aabbbccc

If I chose:

x = aa

y = b

z = bbccc

then xy or aab <= p and y > 0. Then if I pump up y by 2 for example, I would get the string aabbbbccc. But this is not in the language as there are more b's then c's. The problem i'm having is if I instead split my string as such:

x = a

y = a

z = bbbccc

then xy or aa <= p and y > 0. If I pump this string by 2 for example, I would get the string aaabbbccc, which is in the language. So in this case the pumping lemma is passed.

So my question is, for the pumping lemma does my second example passing mean that the language a^nb^mc^m passes the pumping lemma, or does the fact that I found a case where splitting x and y with this pumping length makes it false, mean that the language does not pass the pumping lemma. And if that is the case then if I had the language:

a^nb^m where n >=0 and m >=0 and I choose m to be p, and made the pumping length 3 for example, I could end up with the string:

aabbb, where x = a, y = ab, z = bb, which when pumped would produce aababbb which is not in the language, but I know that a^nb^m is a regular language.

Hopefully you can see where my confusion lies. I been researching for a while and I just can't find a clear cut answer on this. Any help would be extremely appreciated.

Thank you.

Apply the pumping lemma on the word $$b^nc^n$$.
• In order to use the pumping lemma to show that a given language is not regular, you have to find, for each integer $n$, a word of length at least $n$ in the language, such that for each legal decomposition, you can pump it out of the language. I suggest reviewing the statement of the pumping lemma. – Yuval Filmus Jul 13 at 15:19