3

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 :)

Community
  • 1
  • 1
hqt
  • 29,632
  • 51
  • 171
  • 250

1 Answers1

4

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.

nneonneo
  • 171,345
  • 36
  • 312
  • 383
  • Can you tell me more, please. Because, I see that CSG has some condition for context, but CFG. so, I think, CSG should be special case of CFG – hqt Oct 17 '12 at 04:59
  • Can you give me some examples, and tell me difference, thanks :) – hqt Oct 17 '12 at 04:59
  • A CFG is equivalent to a CSG where every rule has an empty string for both left and right context. Therefore, every CFG can be written as a CSG, but not every CSG can be written as a CFG. So, by definition, a CFG is a special case of a CSG. – nneonneo Oct 17 '12 at 05:13