If you want to make money online : Register now

[Answers] What does $CS - CF$ means?

, , No Comments
Problem Detail: 

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.

Asked By : kate

Answered By : Lieuwe Vinkhuijzen

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$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/47893

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback