# 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. Oct 5, 2015 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, 2015 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, 2015 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$.
• 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. Oct 5, 2015 at 16:58
• @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. Oct 5, 2015 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. Oct 5, 2015 at 22:51