On Thu, Oct 25, 2001 at 10:42:44AM +0100, Ian Phillipps wrote:
> I don't normally like to butt into a private conversation,
:-) I hope this doesn't seem like a private conversation -- otherwise
it shouldn't be on a public mailing list! :-)
> but could someone explain to me (I'm only here for the the Fun, you
> see) what CSL and PSPACE is?
I suspect that I have a strange idea of Fun (perhaps I should start a
list called "Fun with formal languages, complexity theory and
non-standard logic", where I'll presumably be the only subscriber).
Back in the 1950s, a young linguist called Noam Chomsky was looking
for a way to describe grammar mathematically. In 1956, he published a
paper called _Three models for the description of language_ which
describes some ideas which have become the basis for most subsequent
work in computational linguistics.
The simplest model is the "regular languages", which had been
introduced two years earlier by Stephen Kleene. They're the languages
that can be described by simple regular expressions.
Next up comes the "context-free languages". The syntax of some
programming languages is context-free. (Our own beloved Perl is a
notable exception.) A context-free language (CFL) can be described by
a so-called context-free grammar (CFG), which is a collection of
rewriting rules like this:
Sentence -> NounPhrase TransitiveVerb NounPhrase
Sentence -> NounPhrase IntransitiveVerb
Sentence -> NounPhrase 'is' Adjective
NounPhrase -> Adjective NounPhrase
NounPhrase -> Noun
Noun -> 'Perl'
Noun -> 'Java'
Noun -> 'FWP'
TransitiveVerb -> 'likes'
IntransitiveVerb -> 'rules'
IntransitiveVerb -> 'sucks'
Adjective -> 'cool'
Adjective -> 'obfuscated'
The idea is that you start with a symbol like 'Sentence', then
successively apply whatever rules you like. When you end up with
something that consists entirely of literals, that's a sentence. So:
Sentence -> NounPhrase TransitiveVerb NounPhrase
-> Noun TransitiveVerb NounPhrase
-> Noun TransitiveVerb Adjective NounPhrase
-> Noun TransitiveVerb Adjective Adjective NounPhrase
-> Noun TransitiveVerb Adjective Adjective Noun
-> 'FWP likes cool obfuscated Perl'
At each stage, we're just applying one of the rewriting rules.
Now, you'll notice that all the rewriting rules just have *one* symbol
on the left. If we relax this restriction, we can get
context-sensitive grammars (CSGs). The idea is that we can constrain
rules so that they can only be applied in certain "contexts", when
they have certain other symbols to their left or their right.
In Perl, if you have a bareword followed by an expression, that
can be interpreted as a function call *only if the bareword is the
name of a function which has already been declared*. That's an
example of context-sensitivity. These two programs are parsed very
differently, even though they both define the same functions and
contain exactly the same text:
sub X::foo {print "X\n"}
$bar = bless [], "X";
foo $bar;
sub foo {print "main\n"}
vs
sub X::foo {print "X\n"}
sub foo {print "main\n"}
$bar = bless [], "X";
foo $bar;
Full CSGs are a *very* powerful tool. So powerful, in fact, that
they're not very useful in computing. It can take an extraordinary
amount of time to parse a string using a CSG.
That's what PSPACE-complete means. If a problem is PSPACE-complete,
that's a formal way of saying there's a snowflake's chance in hell
that anyone will ever find a general algorithm to solve it quickly.
(I *was* intending to give a quick rundown of why that is true, but
I've rambled on long enough already for now. Does anyone fancy taking
up the story at this point?)
.robin.
PS. There's a CSG for generating prime numbers (including a delightful
obfuscated C program) at http://members.fortunecity.com/brank/tor/primes/
