Possible Duplicate:
Context-sensitive grammar and Context-free grammar
In my textbook, here is the explain of these two terms :
Context Sensitive Grammar:
grammar can have productions of the form w1 → w2, where w1 = lAr and w2 = lwr, where A is a nonterminal symbol, l and r are strings of zero or more terminal or nonterminal symbols, and w is a nonempty string of terminal or nonterminal symbols. It can also have the production S → λ as long as S does not appear on the right-hand side of any other production.
Context Free Grammar:
grammar can have productions only of the form w1 → w2, where w1 is a single symbol that is not a terminal symbol. A type 3 grammar can have productions only of the form w1 → w2 with w1 = A and either w2 = aB or w2 = a, where A and B are nonterminal symbols and a is a terminal symbol, or with w1 = S and w2 = λ.
In my textbook, the author said : CSG is a special case of CFG. But, I don't get this point. because in CSG, lAr -> lwr. l and r can be strings of zero or more terminal or nonterminal. So, when it is a string of zero (means : length = 0). we can write lAr as A. So, CSG will be CFG. So, CSG is CFG
Does something I have understand wrong ? Please correct it for me.
Thanks :)
The textbook is in error. As you say, a CFG is a special case of a CSG.
CSGs can express strictly more languages than CFGs can.