|Generating strings from regular expressions email@example.com (KSG) (1999-05-24)|
|Re: Generating strings from regular expressions Helmut.Richter@lrz-muenchen.de (1999-05-27)|
|Re: Generating strings from regular expressions firstname.lastname@example.org (Jonathan Barker) (1999-05-27)|
|Re: Generating strings from regular expressions email@example.com (Carsten Fritz) (1999-05-27)|
|Re: Generating strings from regular expressions firstname.lastname@example.org (1999-05-27)|
|From:||Helmut.Richter@lrz-muenchen.de (Helmut Richter)|
|Date:||27 May 1999 00:43:01 -0400|
|Organization:||Leibniz-Rechenzentrum, Muenchen (Germany)|
KSG <email@example.com> writes:
>Does anyone know of any code or an algorithm that does the following:
>input: a regular expression, R, and an integer k.
>output: a list of all strings of length k that are in R
For a given regular expression and a given symbol, it is relatively
easy to compute a regular expression for what can follow this
symbol. Repeat this process k times. Constructing an expression for L'
such that the original L is aL'|L" such that no word in L" begins with
a has been called the derivative of L with respect to a. There is a
paper by Janusz Brzozowski with this title (Derivatives of Regular
Expressions). It must have appeared in CACM in the 60ies or early
70ies. The paper is quite cute, but if you only need the formulas for
the derivatives, you can make them up on your own.
Return to the
Search the comp.compilers archives again.