# How to show that a language is strictly context sensitive

During a class, we was asked how to prove that a language L is strictly context-sensitive. In particular, we have to prove that

$L = \{a^nb^nc^n \mid n > 0\}$

Could you help me to find the answer providing a detailed solution?

My approach:

I know that a language is strictly of type $n$ if there isn't a type-$j$-grammar ($j > n$) that can generate it.

So i wonder if i can apply the Pumping Lemma for Context Free Languages to prove that.

• To prove a language is strictly RE, you'd have to prove it's RE and not context-sensitive. But that language is context-sensitive (in fact it's the very first example on wikipedia). – cardobard_box Nov 7 '17 at 16:41
• "Pumping Lemma for Context Free Languages" -- that can be used to show that the language is not context-free -- see here -- but not that it's not context-sensitive. – Raphael Nov 7 '17 at 17:35
• I made a mistake. I need to prove that $L$ is strictly context-sensitive. If the language is not context-free, then maybe is context-sensitive. But how to prove the "strictness" ? Showing a context-sensitive grammar for it? – Jack Nov 7 '17 at 17:45
• The strictness you prove by showing that the language is not context-free, for example via the Pumping Lemma (I guess in your nomenclature CF is type 2 and CS type 1, so you need to prove that it is not type 2). The other part of the proof is showing that L is context-sensitive/type 1, for example by describing an LBA for it. – Peter Leupold Nov 10 '17 at 13:21