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 context-free grammar has rules of the following form:
>
> A -> B C D ...
>
> A context-sensitive 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 context-sensitive 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 context-sensitive grammar has
the form aAb -> agb; in particular, every rule of a context-sensitive
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 context-free grammar is also context-sensitive. (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
context-sensitive grammar is one that is *not* context-free, wihch is
not always the case, and also that a context-free grammar is not
context-sensitive, which is false in every case. It might be (perhaps
you know the source texts) that Chomsky used the terms 'type-1 grammar'
and 'type-2 grammar', and 'context-sensitive' was originally taken to
mean 'type-1 but not type-2', which would be more intuitive. (09)
vQ (010)
_________________________________________________________________
Message Archives: http://ontolog.cim3.net/forum/ontolog-forum/
Subscribe/Config: http://ontolog.cim3.net/mailman/listinfo/ontolog-forum/
Unsubscribe: mailto:ontolog-forum-leave@xxxxxxxxxxxxxxxx
Shared Files: http://ontolog.cim3.net/file/
Community Wiki: http://ontolog.cim3.net/wiki/
To Post: mailto:ontolog-forum@xxxxxxxxxxxxxxxx (011)
|