grammarpumping-lemmacontext-sensitive-grammar

Pumping lemma for context-sensitive language?


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?


Solution

  • 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.