I have a question involving the Pumping Lemma for Regular Languages and Pumping Lemma for Context-free Languages: Is it possible that there's a language which doesn't meet the criteria for the pumping-lemma for context-free languages but does meet the criteria for the pumping-lemma for regular languges?
Or is there a hierachy similar to the Chomsky-Hierachy?
I'm just trying to understand that and pumping lemma in general
Is it possible that there's a language which doesn't meet the criteria for the pumping-lemma for context-free languages but does meet the criteria for the pumping-lemma for regular languges?
Let's consider the classic a^nb^n language. aabb is in it, while abb is not.
We know it is a CFL. (S -> aSb | epsilon)
We can proof that is is not a regular language using the PL for CFL (cf. https://stackoverflow.com/a/2309755)
The PL for CFL is used to proof that a language is NOT CF. But the language IS CF (see above!).
Thus we can never use the PL for CFL for the language to proof that is it not CF.
A regular language [...] must be a CFL itself and therefore should be able to meet the PL criteria for CFL or am I wrong?
Yes, any RL is also a CFL (and also a CSL and also a REL). You are wrong in your conclusion though.
The PL is used to proof that a given language is NOT in the class. So we use the PL for RL to show that a language is not a RL, so "at most" CF. And we use the PL for CFL to show that a language is not even a CFL, so "at most" context sensitive.
Is there a hierarchy similar to the Chomsky-Hierarchy ?
Well if you can proof a language is not context free, it can also not be regular, as RL is a subset of CFL.
