Languages and their relation : help

Question

This is not a homework question though, this is something I wish to know to add to my own knowledge.

While reading one of the texts on automata (K.L.P. Mishra, "Theory of Computer Science : Automata, Languages and Computation," third ed. Languages and their relation, Chapter 4, Page 123), I came across the following property

If $L_{0}, L_{cfl}, L_{csl} $ and $ L_{rl} $ denote the family of type-0 languages, context-sensitive languages, context-free languages, and regular languages, respectively, then

Property 2 : $L_{cfl} \subseteq L_{csl}$

and

Property 4 : $L_{rl} \nsubseteq L_{cfl} \nsubseteq L_{csl} \nsubseteq L_{0}$

Can anyone please explain Property 2 with a formal proof, apart from the fact that it is apparent from Chomsky's hierarchy? Also, howcome Property 4 is true if Chomsky's hierarchy were to be followed? This seems to be a contradiction in its own to me.

Answer 1

Property 2 is immediate from the definitions: $L_{csl}$ is defined as the family of languages generated by a context-sensitive grammar. $L_{cfl}$ is the family of languages generated by a context-free grammar. Every context-free grammar is trivially a context-sensitive grammar, because a context-free grammar is defined to be a context-sensitive grammar that satisfies certain additional properties.

You are confused about the notation in Property 4. It does not say $L_{rl}\not\subseteq L_{cfl},ドル it says $L_{rl}\subset_\ne L_{cfl}$:

Annoying notation

I guess that "$A \subset_\ne B$" here is an abbreviation for "$(A\subseteq B) \text{ and } (A\ne B)$". With this interpretation, the claim of Property 4 is correct. (Annoyingly, the book appears not to explain this nonstandard notation, either in the section on "mathematical preliminaries" or in the table of notation on pages xi–xiii.) The standard notation for this relation is "$\subsetneq$"; one reads it as "$A$ is a proper subset of $B$".