John F. Sowa wrote:
>
> As I have said, the only coherent notion is the syntactic one.
> And a related syntactic notion appears in the literature of
> linguistics and comp. sci. in the notion of a "context free"
> vs. a "context sensitive" grammar.
>
> A contextfree grammar has rules of the following form:
>
> A > B C D ...
>
> A contextsensitive grammar has one or more rules of
> the following form:
>
> x A y > x B C D ... y
>
> where x and y are arbitrary strings that specify the
> "context" that is required as a prerequisite for using
> this rule.
>
Worth noting that a contextsensitive grammar is one in which rules are
of the form (01)
aAb > agb (which maps to what you state above), (02)
where a, b, and g (usually written as alpha, beta, and gamma) are *any*
strings of terminals and nonterminals, of which only g must be
nonempty. (A is a nonterminal.) Following that, a rule of the form (03)
A > g (04)
*is* also of the form (05)
aAb > agb (06)
where a and b are simply the empty string. (07)
It's usual to say that *every* rule in a contextsensitive grammar has
the form aAb > agb; in particular, every rule of a contextsensitive
grammar can be of the form A > g, if for all rules in that grammar a
and b are the empty string. Consequently, and in accord with the
Chomsky's hierarchy, every contextfree grammar is also contextsensitive. (08)
This terminology is unintuitive to me, but this is how it seems to
work; I found it common among my colleagues to think that a
contextsensitive grammar is one that is *not* contextfree, wihch is
not always the case, and also that a contextfree grammar is not
contextsensitive, which is false in every case. It might be (perhaps
you know the source texts) that Chomsky used the terms 'type1 grammar'
and 'type2 grammar', and 'contextsensitive' was originally taken to
mean 'type1 but not type2', which would be more intuitive. (09)
vQ (010)
_________________________________________________________________
Message Archives: http://ontolog.cim3.net/forum/ontologforum/
Subscribe/Config: http://ontolog.cim3.net/mailman/listinfo/ontologforum/
Unsubscribe: mailto:ontologforumleave@xxxxxxxxxxxxxxxx
Shared Files: http://ontolog.cim3.net/file/
Community Wiki: http://ontolog.cim3.net/wiki/
To Post: mailto:ontologforum@xxxxxxxxxxxxxxxx (011)
