Re: Context Sensitive Languages (Was Re: Uses for CSS?)

-----Original Message-----
From: John M. Allen <jallen(at)thunder.ocis.temple.edu>
To: Ben Z. Tels <optimusb(at)stack.nl>
Cc: hwg-theory <hwg-theory(at)hwg.org>
Date: dinsdag 2 juni 1998 16:31
Subject: Re: Context Sensitive Languages (Was Re: Uses for CSS?)


>I suggest you check out
><http://www.netaxs.com/people/nerp/automata/chomsky1.html> which discusses
>Context Sensitive Languages and Grammars. In particular, check out
><http://www.netaxs.com/people/nerp/automata/chomsky4.html>which gives the
>hierarchy as


Very interesting. Not exactly astounding, but interesting.
The Chomsky Hierarchy is also in "An Introduction to....", chapter 11,
section 4.

Given the hierarchy Chomsky gave it, this hierarchy also lists the name
"context-sensitive languages". It is given as a name for a special subset of
the Turing-calculable languages, which is how it fits in our classification.
As Turing-calculable, not part of the context-free languages.

>Regular Language
>Context-free Language


Up to here.

>Context-sensitive Language
>Recursively Enumerable Language


All covered as Turing-calculable.

>Saying that Context-sensitive Languages do not exist does not make it so.

It is the name you give them. We do not use it.

>You
>are wrong. Admit it. It is painful obvious to anyone willing to check out
the
>URLs listed above.


All of it is Turing-calculable. That is how it was taught, that is how I
stand.

>I would also question the quality of your reference if it makes no mention
of
>Context Sensitive Languages. I think it's time that you get another
reference.


It does. Once. As another name for something else.
However, after that statement, I will admit you have brass cohones.
"An Introduction to Formal Languages and Automata" was written by Peter
Linz, professor at the University of California at Davis and is used as a
textbook in a first-year course at the Technical University of Eindhoven, a
university noted throughout the world for having one of the best curricula
on logic to be found. Takes some doing to question their choice of
literature.

Ben Z. Tels
optimusb(at)stack.nl
http://www.stack.nl/~optimusb/

"The Earth is the cradle of the mind, but one cannot stay in the cradle
forever."
                                                    --Tsiolkovsky

HWG hwg-theory mailing list archives, maintained by Webmasters @ IWA