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$?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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."
