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

Glenn Jackman wrote:
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$


Yes, but the set of all subsets of S is not the same as the set of single strings in S (i.e. S).

DS
.

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)