Pumping lemma for context-sensitive language?

Question

i have googled on pumping lemma for context sensitive, and it seems to only produce results for context-free language.

Pumping lemma only allows to prove a language is context free only? and not context sensitive?

Any idea how?

Answer 1

There are two Pumping Lemmas. Pumping Lemma for regular languages allows to prove that a language is not regular. Pumping Lemma for context-free languages allows to prove that a language is not context-free and hence not regular.

There are no other Pumping Lemmas. To prove that language is context sensitive you could first using Pumping Lemma prove that it is not context-free. Then you must supply a context sensitive grammar that actually generates given language.

Answer 2

Pumping lemmas exist for regular, context-free, tree-adjoining, and multiple-context-free languages. There is a good survey in Johan Behrenfeld's master's thesis:

http://www.flov.gu.se/digitalAssets/1302/1302983_behrenfeldt-johan-alinguists.pdf

There is no pumping lemma for context-sensitive languages. Indeed, this class has considerably more generative power, and include languages without any kind of "pumping" property, e.g. {a^p | p prime}.

Each pumping lemma states a property that is true of a language in that class. It can be used to prove that a language is not in that class, as a proof by contradiction. It cannot be used to prove that a language is in that class.

Answer 3

The "pumping lemma-like" approach for tree-adjoining languages actually is named the "pumping lemma for tree-adjoining languages" everywhere in the literature. It makes it possible to prove that a language is not tree-adjoining, and therefore not mildly context-sensitive. Maybe this is the one you had in mind?

It was defined by Vijay-Shanker in his PhD thesis, which is unfortunately not available online. It is nonetheless easy to find how it works by searching the web. Many courses, for instance this one from the University of Tübingen, give a good account.