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.

  • 2
    $\begingroup$ 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. $\endgroup$ – wvxvw Oct 5 '15 at 14:37
  • $\begingroup$ Note: we often denote with CSL and CFL the context sensitive resp. free languages and with CS/FG the grammars. $\endgroup$ – Raphael Oct 5 '15 at 15:05
  • $\begingroup$ Thank you for your comment. I thought it is well known in formal languages that CS means family of context-sensitive languages.. $\endgroup$ – 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$.

| cite | improve this answer | |
  • $\begingroup$ Thank you very much for your kind explanation. That really helps! especially the "context-sensitive can count" insight. $\endgroup$ – kate Oct 5 '15 at 16:44
  • $\begingroup$ 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. $\endgroup$ – Lieuwe Vinkhuijzen Oct 5 '15 at 16:58
  • $\begingroup$ 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! $\endgroup$ – kate Oct 5 '15 at 17:06
  • 1
    $\begingroup$ @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. $\endgroup$ – Hendrik Jan Oct 5 '15 at 20:23
  • $\begingroup$ @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. $\endgroup$ – Lieuwe Vinkhuijzen Oct 5 '15 at 22:51

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.