Re: The inverse problem: generate all instances of a regexp

From: "Ingo Menger" <quetzalcotl@xxxxxxxxxxxxxx>
Date: 15 Feb 2006 09:51:15 -0800

bugbear schrieb:

Andrei Alexandrescu (See Website For Email) wrote:

I wonder how this could be done elegantly. Given a regular expression
$re, write a function Generate($) that returns a list of all possible
strings that could match $re. If the set is infinite, die with an error
message.

The latter sounds like the "halting problem"

No, its trivial.
Any regex containing {n,} describes an infinite set. Note that * is
short for {0,} and + is short for {1,}.
The rest describe finite sets. The proof is easily done by examining
all remaining regex constructs and finding either
- that the set of strings that'd match is finite (such as a character
standing for itself or a character class),
- or that the given way of combining sets is finite as long as there
are no infinite sets

It is assumed, of course, that the regex is anchored on both sites,
i.e. it has to match the whole string (/^re$/). Otherwise, it would
describe an infinite set (/^re/ or /re$/) in any case.
It is also assumed that the set of characters is finite.

.

Follow-Ups:
- Re: The inverse problem: generate all instances of a regexp
  - From: Ilya Zakharevich

References:
- The inverse problem: generate all instances of a regexp
  - From: Andrei Alexandrescu (See Website For Email)
- Re: The inverse problem: generate all instances of a regexp
  - From: bugbear

Prev by Date: Re: How to stop perl from exiting when stat($_)->size fails
Next by Date: Re: How to stop perl from exiting when stat($_)->size fails
Previous by thread: Re: The inverse problem: generate all instances of a regexp
Next by thread: Re: The inverse problem: generate all instances of a regexp
Index(es):
- Date
- Thread

Relevant Pages

Re: infinity
... > of any given word in the language. ... When I add one character to string X, ... can add an infinite number of characters, and the string is no longer finite. ... The the strings are not finite, ...
(sci.math)
Re: How to exclude a string using regexp pattern?
... >> From the following log.txt file, if I want to remove the other strings ... >> Or I have to create a new java program to do this? ... > negated character classes, ... That part of the regex will match everything up ...
(comp.lang.java.programmer)
Re: Cantor and the binary tree
... > That's because it's actually infinite, as opposed to your set of finite, ... > terminated strings, which is not. ... must be able to tell us what happens when one appends one more character ...
(sci.math)
Re: Cantor and the binary tree
... >> That's because it's actually infinite, as opposed to your set of finite, ... >> terminated strings, which is not. ... Not unless you are only talking about terminating binary ... > must be able to tell us what happens when one appends one more character ...
(sci.math)
Re: infinity
... > For ANY finite length L, there are a finite set of strings of length L or less. ... > For which L in N is the set of all strings up to that length an infinite set? ... the sets of strings of one character. ... By induction, the property holds for every set of finite ...
(sci.math)