On Tue, Feb 17, 2009 at 8:19 PM, Yigal Chripun <[email protected]> wrote: > context-sensitive means that you need to have both the context and the > language phrase to derive "semantic" meaning.
No, context-sensitive refers to the left-hand side of a grammar (rewrite) rule. A CFG is restricted in the sense that the left hand side of a grammar rule can only be one non-terminal. The right hand side can contain terminals, non-terminal, and epsilons. E.g.: NP --> Det N is a valid CFG rule. An unrestricted grammar allows (one or more) terminals and non-terminals on the left hand side. A context-sensitive grammar is like an unrestricted grammar, but does not allow for epsilons on the left or right hand sides. Some surface strings can not be described by finite grammars that can be described by a context-free grammar, such as AnBn (n A's followed by n B's). Likewise, some surface strings can be described by an unrestricted grammar that can not be described by a context-free grammar (such as AnBnCn). We're not talking semantics here, just surface strings ;). Of course, extracting semantics can be a side-effect of parsing. Take care, Daniel
