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.

asked Nov 7 '17 at 16:35

Jack

729 bronze badges

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

add a comment |

0 Your Answer

Name

Required, but never shown

Post as a guest

Name

Required, but never shown

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