Considering this language $L = \{a^n b^m c^{n+m} \mid n, m \geqslant 0 \}$ is it a CFL? If I can make a PDA for it can I still prove with the pumping lemma that the language is not CFL?
I mean if try first to use pumping lemma to prove that it's not CFL then:
Let $w = uvxyz$, then choose $n = 2$ such that $uv^ixy^iz$
then $uxy$ would have in some cases $a$'s and $b$'s or just $b$'s or just $a$'s or $c$'s anyway if I pump it than $w$ will habe more $c$'s then $b$'s and $a$'s.
So in this case it's still not a CFL?
Best Answer
It is context free. A grammar for it is:
$$S\to aSc \mid T\\T \to bSc \mid \varepsilon$$
This is because $a^Mb^Nc^{M+N}$ is the same as $a^Mb^Nc^Nc^M$, which means you can build it from the inside out.
Your argument using the pumping lemma doesn't work. Roughly speaking, the pumping lemma says: "If a language is context-free, then every sufficiently long string is pumpable. This means that there exists a number $p$, such that all strings in the language longer than length $p$ are sufficiently long. And for every sufficiently long string, there exists a way to subdivide it such that it is pumpable and satisfies all the requirements of the pumping lemma."
In order to show that a language is not context-free, you have to show that:
For every value of $p$,
There exists a string $s$ in the language which is longer than $p$, such that
For every possible way you can divide up the string into $s=\mathsf{uvwxy}$, the string fails to be pumpable:
Either the string produces results that aren't in the language (so there is some $k\geq 0$ such that $\mathsf{uv}^k\mathsf{wx}^k\mathsf{y}$ isn't in the language.), or the subdivision $s=\mathsf{uvwxy}$ violates one of the pumping lemma rules $|\mathsf{vx}|\neq 0$ or $|\mathsf{vwx}|<p$.
If you can show these steps, you prove that the language is not context-free. But you cannot use the pumping lemma in an argument like this: