Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!wuarchive!cs.utexas.edu!tut.cis.ohio-state.edu!n8emr!uncle!basho!john
From: john@basho.uucp (John Lacey)
Newsgroups: comp.lang.c
Subject: Re: Summary: 'C', is it's grammar context sensitive ?
Summary: Clear up types of grammars.
Message-ID: <1990Sep2.012002.7004@basho.uucp>
Date: 2 Sep 90 01:20:02 GMT
References: <1990Aug30.223440.7377@NCoast.ORG> <11508@crdgw1.crd.ge.com>
Organization: Sportsware
Lines: 37

In article <1990Aug30.223440.7377@NCoast.ORG> of comp.lang.c
    ramsey@NCoast.ORG (Cedric Ramsey) writes:
} If you guys agree that 'C' is context sensitive then what languages
} truely are context-free, if any. 

In article <11508@crdgw1.crd.ge.com> of comp.lang.c
    volpe@underdog.crd.ge.com (Christopher R Volpe) writes:
} Let's clarify some terminology here: First, all context free languages
} are context sensitive and all context free grammars are context sensitive.
} There is a hierarchy involved here. The concepts are not mutually
} exclusive, but rather the former is a superset of the latter. When you
} say "context sensitive", you really mean "non context free". 

This seems hardly a clarification.  You say all A are B and all B are A,
then claim there is a hierarchy in the next sentence.

There *is* a hierarchy.  But "context sensitive" is not the same as
"non context free".  The set of context-sensitive grammars is a superset
of the set of context-free grammars.  This implies that all context-free
grammars are context-sensitive, but not all context-sensitive grammars
are context-free.  The correct statement, then, is that C (as a complete
language) is context-sensitive but not context-free.

In brief, Chris said S <= F and F <= S and that C is ~F, when in fact,
F < S, and C is in (S - F). (All where F = context-free and 
S = context-sensitive.)

Any further discussion on this topic belongs in comp.theory.

Toodles and cheers,

John
-- 
John Lacey, 
   E-mail:  ...!osu-cis!n8emr!uncle!basho!john  (coming soon: john@basho.uucp)
   Voice:   (614) 436--3773, or 487--8570
"What was the name of the dog on Rin-tin-tin?"  --Mickey Rivers, ex-Yankee CF