OT -- Re: random cover of a range

[Daniel de Kok]

On Tue, Feb 17, 2009 at 8:19 PM, Yigal Chripun <yigal100 at gmail.com> 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