Swapping lecture for context-sensitive language?

Question

I have googled to a pumping lemma for context-sensitive and this seems to only produce results for a context-free language.

Does pumping lemma only prove that language is only context free? and does not depend on the context?

Any idea how?

Answer 1

There are two pump lemmas. The pump lemma for regular languages ​​allows us to prove that the language is not regular. Neglecting the lemma for context-free languages ​​allows us to prove that a language has no context and, therefore, is not regular.

There are no other pumping lemmas. To prove that the language is context sensitive, you can first use Pumping Lemma to prove that it is not contextual. Then you must provide the context-sensitive grammar that actually generates the given language.

Answer 2

The "lemma-like" pumping "approach for tree-like languages ​​is actually called the" lemma on pumping a tree adjacent to languages ​​"throughout the literature. This allows us to prove that the language is not related to trees and, therefore, is insensitive to context. Maybe this is the one which do you mean?

He was identified by Vijay-Shanker in his Ph.D. thesis, which , unfortunately, is not available on the Internet. However, it’s easy to find how this works when searching on the Internet. Many courses, like this one from the University of Tübingen, give you a good account.

Answer 3

Pump lemmas exist for regular, context-free, tree-related, and non-context-free languages. Johan Behrenfeld has a good overview:

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

A lecture lecture for context-sensitive languages ​​is missing. Indeed, this class has significantly greater generative power and includes languages ​​without any “pumping” property, for example. {a ^ p | p prime}.

Each pump lemma contains a property that corresponds to the language of this class. It can be used to prove that language is not in this class, as proof by contradiction. It cannot be used to prove that a language is in this class.