Re: Construction of a non-regexable subset of the set of all strings

At 2006-06-23 08:45AM, Dominic van der Zypen <dominic.zypen@xxxxxxxxx> wrote:
Hello,

I have a question which I am afraid might seem "overly scientific" (not
to say nutty), but which I find is quite natural after all.

If we look at the set S of all finite strings, then each regex
represents some subset of S. For instance, h(a|e)ndel is the set
consisting of handel and hendel; and the regex .+ represents the set
of all non-empty strings not containing \n.

I wondered whether there is a "non-regexable" subset N of S (i.e. a
subset N for which there is no regex representing N) and came up with
a (non-constructive) positive answer from set theory: there are
uncountably many subsets of S, but there are only countably many
regular expressions, so there are non-regexable subsets.

What I would like to know is whether one can construct a subset N of S
which is non-regexable (and whether it is hard to prove that N has the
desired property).

It seems to me that, for every string x in S, one can construct at least
one regular expression to match it, i.e. ^x$

--
Glenn Jackman
Ulterior Designer
.

Relevant Pages

  • Re: for a laught (???)
    ... Regex doesn't work too well with a null byte delimiter :-) ... the API for a particular form of regular expressions ... Regex doesn't work with null terminated strings. ... qualifier or the qualifier "commonly" might have suggested. ...
    (comp.lang.cobol)
  • Re: Construction of a non-regexable subset of the set of all strings
    ... I have a question which I am afraid might seem "overly scientific" (not ... If we look at the set S of all finite strings, then each regex ... regular expressions, ...
    (comp.lang.perl.misc)
  • Re: A string-replace?
    ... to cl-ppcre:regex-replace, only without the regex. ... is there a good way to escape ... regular expressions so they would be treated as strings by ppcre (the ...
    (comp.lang.lisp)
  • Re: Construction of a non-regexable subset of the set of all strings
    ... I have a question which I am afraid might seem "overly scientific" (not ... If we look at the set S of all finite strings, then each regex ... Are you talking about regular expressions in general or only Perl's regular ...
    (comp.lang.perl.misc)
  • Re: A string-replace?
    ... to cl-ppcre:regex-replace, only without the regex. ... is there a good way to escape ... regular expressions so they would be treated as strings by ppcre (the ...
    (comp.lang.lisp)