3
$\begingroup$

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!

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

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.