0
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ 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). $\endgroup$ – cardobard_box Nov 7 '17 at 16:41
  • $\begingroup$ "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. $\endgroup$ – Raphael♦ Nov 7 '17 at 17:35
  • 1
    $\begingroup$ 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? $\endgroup$ – Jack Nov 7 '17 at 17:45
  • $\begingroup$ 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. $\endgroup$ – Peter Leupold Nov 10 '17 at 13:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.