Re: [FWP] japhy had a silly idea...

[andrew@pimlott.ne.mediaone.net (Andrew Pimlott)]

On Mon, May 28, 2001 at 08:30:39PM -0400, Bernie Cosell wrote:
> On 28 May 2001, at 22:57, Abigail wrote:
> > Well.... only if you match against finite strings. However, regexes
> > can match infinite strings as well.
> 
> No they can't.  What you're saying is meaningless on two fronts: first 
> you seem to have a somewhat fuzzy notion of what an 'infinite string' is, 
> and second you have an equally fuzzy notion of what a "match" is against 
> a grammar/expression.  Even context-sensitive expressions [i.e., touring 
> machines, which are *broader* than even Perl REs] can only generate 
> countable languages.

None of abigail's notions are fuzzy; in fact, they are very precise.
(If you read carefully, you will notice that abigail is consistently
precise.)  If he doesn't spell them out, it is (I think) because he
intends to challenge you.  I may spoil his Fun this time.

An infinite string is a map from Z+ (postivite integers) to
characters.

To talk about a grammar generating an infinite string, you do have
to extend the definitions, but the extensions are straightforward.
For example, you can define "A*" to generate all (possibly infinite)
strings comprised of (possibly infinitely many) substrings, each of
which matches "A".  Some of the fancy constructs in Perl re's (eg,
those that involve arbitrary Perl code) can't be extended, but all
the conventional elements can.

Obviously, you can't test for matches against infinite strings with
the usual algorithms; however, this does not invalidate the concept.

> > .. And since there is an obvious,
> > 1-to-1 mapping between the set of reals between 0 and 1 and the set of
> > strings (including the infite length strings) consisting of digits only,
> > and each such a string is matched by /^\d+$/, it's not true that a set
> > matched by a regex is of countable size.
> 
> First off, there is *NO* 1-1 such mapping, but that's a math subtlety 
> that doesn't really matter, obvious to you or not.

Be assured that Abigail has a firm grasp of such subtlety (and that
there is such a mapping, which I think you can figure out if you
haven't already).

> but more clearly, you're just wrong on the face of it.  First, going from 
> the RE to the language, you can enumerate every string that /^\d+$/ 
> matches and the set will be completely countable.  Period.

IMO, refusing to allow re's to match infinite strings is no Fun.

Andrew

==== Want to unsubscribe from Fun With Perl?  Well, if you insist...
==== Send email to <fwp-request@technofile.org> with message _body_
====   unsubscribe