2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

Apply the pumping lemma on the word $b^nc^n$.

$\endgroup$
  • $\begingroup$ Thank you for the answer. So with the pumping lemma, do you only have to find a situation when the pumping lemma does not hold for the language, even if there are some configurations where it does? $\endgroup$ – Nitromario Jul 13 at 15:17
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Jul 13 at 15:19
  • $\begingroup$ Thank you again for the answer. So for example, with my example a^nb^mc^m, does this mean that, if I select the variable n to be used for my pumping length, that the pumping lemma does not show that this language is not regular, because no matter how many times you pump a, it does not effect b and c? $\endgroup$ – Nitromario Jul 13 at 15:33
  • $\begingroup$ The pumping lemma does show that your language is not regular. You just have to choose a different word. $\endgroup$ – Yuval Filmus Jul 13 at 15:35
  • $\begingroup$ Ok, thank you again, I believe that I understand now. $\endgroup$ – Nitromario Jul 13 at 15:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.