[Top] [All Lists]

Re: [ontolog-forum] Scheduling a Discussion [was: CL, CG, IKL and the re

To: "[ontolog-forum]" <ontolog-forum@xxxxxxxxxxxxxxxx>
From: Wacek Kusnierczyk <Waclaw.Marcin.Kusnierczyk@xxxxxxxxxxx>
Date: Wed, 16 Jan 2008 10:20:36 +0100
Message-id: <478DCC64.3000201@xxxxxxxxxxx>
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)

<Prev in Thread] Current Thread [Next in Thread>