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

-----Original Message-----
From: John M. Allen <jallen(at)thunder.ocis.temple.edu>
To: hwg-theory <hwg-theory(at)hwg.org>
Date: maandag 1 juni 1998 21:17
Subject: Context Sensitive Languages (Was Re: Uses for CSS?)


>> > and it is recognized by finite
>> > linear Turing Machines.
>>
>> Which puts you right back in the realm of context-free languages.
>
>No, it gives you context-sensitive languages.


I was mistaken.... It gives you a subset of all Turing-calculable languages.
Not your context-sensitive languages, by the way. See later on.

>This was only a sample, not necessarily meant to be exhaustive. The primary
>characteristic is that there is a SINGLE NON-TERMINAL on the left hand side
of the
>production rule.


Also not a correct characterization of production rules for context-free
languages:

S -> AB
AB -> aABb
AB -> lambda

>> > whereas in context sensitive languages you can have production rules of
the form
>> >
>> > aA-->aA
>>
>> Equivalent to A -> lambda.A
>
>No. The point is that the left hand side can contain any STRING of
NON-TERMINALS and
>TERMINALS with at least one non-terminal.


S -> aABb | lambda
aABb -> aaABbb | ab

Same language, still not "context-sensitive". If you don't beleive it, try
proving it. Try applying the pumping lemma for context-free languages.

>> Yes, the set of production rules.
>
>No the context of the non-terminal. Above, there is no production rule for
A itself.
>There is only one for A in the context of having a preceding B.


You are speaking of a construction which maintains a state. That's a PDA, or
a Turing machine.
The first is always associated with a context-free grammar, the second with
a Turing-calculable one [0].
Nothing in between.

>> > Context Sensitive is a class of formal language. It is also referred to
as type
>> > 1 languages and are parsed/produced by finite linear Turing machines.
>>
>> Which brings you back to the languages produced by finite automata. The
Context-Free
>> languages.
>
>No, it does not. Let me give you an example. The simplest context-sensitive
language
>that I know is a<sup>n</sup>b<sup>n</sup>c<sup>n</sup>. This would include
strings
>such as abc, aabbcc, aaabbbccc, aaaabbbbcccc,.... It would exclude strings
such as
>aabcbc.


I would take another long hard look at your definition fo context-sensitive
language, because according to that definition your example is not one.
a^n.b^n.c^n is not produced by a finite linear Turing machine; it is not a
finite language.

However, a^n.b^n.c^n IS a Turing-calculable language. You need a normal
Turing machine for it, linear or other (makes no difference whether it is
linear or not). You can prove that it is not context-free using the pumping
lemma. That makes it Turing calculable, which I believe is the proper name
for what you call context-sensitive (or at least most of it).

>You simply cannot reproduce this with a context free grammar.

Yes, I know. I can prove it to you, using the pumping lemma.

>Context sensitive
>languages are not extensions of context free languages. They are a
completely
>different set of languages.


Pascal is produced by a context-free grammar. However, what is compiled by a
Pascal-compiler is the language produced by that grammar, extended with
contextual information.

>I'm not saying that they are disjoint. In fact, context free languages are
a subset of
>the context sensitive languages.

Then they are not a different class of languages (which they are indeed
not). They would have to be disjoint sets for that.

>This started when I mentioned context sensitive
>languages and you said there was no such thing. Do you wish to retract that
statement
>now?


No. There are three types of formal languages [0]:

regular subset of context-free subset of turing-calculable

What is not context-free is turing-calculable.

[0] "An Introduction to Formal Languages And Automata" by Peter Linz

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