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.
$\begingroup$
$\endgroup$
3
-
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$– wvxvwOct 5, 2015 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, 2015 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$– kateOct 5, 2015 at 16:46
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
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$.
answered Oct 5, 2015 at 15:02
-
$\begingroup$ Thank you very much for your kind explanation. That really helps! especially the "context-sensitive can count" insight. $\endgroup$– kateOct 5, 2015 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$ Oct 5, 2015 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$– kateOct 5, 2015 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$ Oct 5, 2015 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$ Oct 5, 2015 at 22:51