Is the pumping lemma for context free languages a generalization of the pumping lemma for regular languages (for instance if we set $u=\epsilon, v=\epsilon$ we can then relate $wx$ in the pumping lemma for CFL to $xy$ in the pumping lemma for regular languages)?
And if so, does this mean if a language fails to satisfy the conditions from the pumping lemma for context free languages, it is not regular?
If this is the case then the statement that: "if a language violates the condition from the Pumping Lemma for context-free languages, it is not regular", is also true?
Many thanks!
Best Answer
The pumping lemma for regular languages states: If $L$ is regular then there exists an $n > 0$, such that for any $x \in L$ with $|x| \geq n$ there exist strings $u, v, w$ such that $x = uvw$, $|uv| \leq n$, $|v| > 0$ and for all $m \geq 0$, $uv^mw \in L$.
The pumping lemma for context free languages states: If $L$ is context free then there exists an $n > 0$ such that for any $x \in L$ with $|x| \geq n$ there exist strings $v, w, x, y, z$ such that $u = vwxyz$, $|wxy| \leq n$, $|wy| > 0$ and for all $m\geq 0$, $uw^mxy^mz \in L$.
Now indeed, if a language $L$ satisfies the conclusion of the pumping lemma for regular languages, then it also satisfies the conclusion of the pumping lemma for context free languages by picking $v = w = \epsilon$ and $x = u$ and $y = v$ and $z = w$, where $u, v, w$ are strings from the conclusion of the pumping lemma for regular languages.
And so what you say is indeed correct. If the conclusion of the pumping lemma for context free languages fails for a particular language $L$ then the language cannot be regular, because the conclusion of the pumping lemma for regular languages must fail for $L$.
However this also follows from the fact that any regular language is context free and in fact can be given by a very simple grammar, called a regular grammar. So if the conclusion of the pumping lemma for context free languages fails, then the language is not context free, which also means that it is not regular.