On Thu, 25 Oct 2001 at 12:56:21 +0100, Robin Houston wrote: > 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! :-) Should have been a smiley.
> 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). Oh, I don't know :-) > 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: The "context sensitivity" bit struck me after I replied. OTOHUAAAPITA. > 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 ... or, of course, if the expression is another bare word that looks like a module name. ~ % perl -e 'hello world' Can't locate object method "hello" via package "world" at -e line 1. > 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. Is it related to NP-complete? > PS. There's a CSG for generating prime numbers (including a delightful > obfuscated C program) at http://members.fortunecity.com/brank/tor/primes/ .... but you can do that sort of thing with Perl's 'R'E, too: grep {('x'x$_)!~/^(..+)\1+$/} 1..1000 or was that your point? The thread has passed me by :-) Ian -- I am confident this explanation will dispell any feelings of certainty that may have been troubling you. - [EMAIL PROTECTED] (Cabbage) in <9601221753.AA27669@spock>
