The language $ L = \{ a^nb^mc^m : n,m \in \mathbb{N} \} $ is non regular. Suppose this needs to be proven using the pumping lemma for regular languages:
Be $ z = ab^nc^n $ such that $ z=uvw, |v| \geq 1, |uv| \leq n $.
Obviously $uv^2w \notin L $ with $ v=b^{k}$ and $ 1 \leq k \leq n-1$.
Is this proof finished now? Or do I need to consider $ v=ab^{n-1} $ as well?
More general: Using the pumping lemma for regular languages, do i need to consider all possible combinations for $uv$?


1 Answer 1


Of course, you have to consider all possible cases. Otherwise you do not prove that "there exists a factorization" is false. So you actually have to consider all $ab^k$ with $k < n$. Here you get some prefix $ab\cdots bab\cdots b$ and therefore the words are outside tha language. Or you chose a different word $z$ if $n=0$ is allowed, which depends on your definition of the natural numbers - then you only have one case.

For the case you treat, probably stating that $uv^2w = ab^{n+k}c^n$ would be more complete than saying "obviously."


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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