Pumping Lemma and Hierachy

Question

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

Answer 1

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.