# What does $CS - CF$ means?

What does $L_1 \in CS - CF$ means?

I think the meaning is $L_1$ can be generated by context-sensitive grammars, but cannot be generated by context-free grammars.

Am I understanding this correctly? Just to be sure.

• It might as well be a molecule of carbon-sulfur-carbon-fluorine, which sounds like a toothpaste component... Perhaps a little more context would help. – wvxvw Oct 5 '15 at 14:37
• Note: we often denote with CSL and CFL the context sensitive resp. free languages and with CS/FG the grammars. – Raphael Oct 5 '15 at 15:05
• Thank you for your comment. I thought it is well known in formal languages that CS means family of context-sensitive languages.. – kate Oct 5 '15 at 16:46

You understand this correctly. the set $CS - CF$ denotes the strict difference between these two levels of the Chomsky hierarchy. If you are reading this in a textbook, you will soon learn that $CS-FS \not= \emptyset$, that is, context-sensitive grammars are strictly more expressive than context-free ones. For example, context-sensitive grammars can count, whereas context-free ones, not so much: the language $\{a^nb^nc^n | n \in \mathbb{N}\} \in CS-CF$.

• Thank you very much for your kind explanation. That really helps! especially the "context-sensitive can count" insight. – kate Oct 5 '15 at 16:44
• Glad to help. You should take the count part with a grain of salt, as I'm not entirely sure how far your can take it. For example, the set $\{a^nb^n | n \in \mathbb{N}\}$ is context-free, and no context-sensitive language can accept the language $\{a^{2^{\left(n^{2}\right)}} | n \in \mathbb{N} \}$. The CFG of $S \rightarrow ASB | \lambda, A\rightarrow a^{k}, B \rightarrow b^{j}$ generates $\{a^{nk}b^{nj}|n \in \mathbb{N} \}$. Other than that, I would have to freshen up on $CSL$ to be more precise on what counting means here. Let's say they can count better. – Lieuwe Vinkhuijzen Oct 5 '15 at 16:58
• You gave me another valuable information. I'm also struggling in knowing whether "this particular language is in this particular class of languages" or not. I guess most people will just say "just try the pumping lemma" etc or ignore without giving any enlighting examples like you did. Many thanks! – kate Oct 5 '15 at 17:06
• @LieuweVinkhuijzen It will be hard to write down a complete grammar, but I do think that your example language $\{ a^{2^{(n^2)} } \mid n\ge 1 \}$ is in fact in CS. As a matter of fact CS is equivalent to LBA, linear bounded automata, Turing machines that can only write on the part of the tape that contains the input. – Hendrik Jan Oct 5 '15 at 20:23
• @HendrikJan You're right, this example is very context-free. The equivalence to LBA was how I came up with the example, but I meant to provide a language which would require an LBA to count to $2^{\left(n^{2}\right)}$, or in general to use $n^2$ space. Instead, this LBA needs only $^2lg(|s|^2)$ space. When I think of one, I'll reply to your comment again. Any $DSPACE(n^2)$ might do (right?), but I'll look out for a particularly simple one. – Lieuwe Vinkhuijzen Oct 5 '15 at 22:51