Return to the
comp.compilers page.
Search the
comp.compilers archives again.
| Related articles |
|---|
| Generating strings from regular expressions kgatlin@cs.ucsd.edu (KSG) (1999-05-24) |
| Re: Generating strings from regular expressions Helmut.Richter@lrz-muenchen.de (1999-05-27) |
| Re: Generating strings from regular expressions ucapjab@ucl.ac.uk (Jonathan Barker) (1999-05-27) |
| Re: Generating strings from regular expressions std10381@moritz.dial.techfak.uni-kiel.de (Carsten Fritz) (1999-05-27) |
| Re: Generating strings from regular expressions djello@well.com (1999-05-27) |
| From: | Helmut.Richter@lrz-muenchen.de (Helmut Richter) |
| Newsgroups: | comp.compilers,comp.theory |
| Date: | 27 May 1999 00:43:01 -0400 |
| Organization: | Leibniz-Rechenzentrum, Muenchen (Germany) |
| Distribution: | inet |
| References: | 99-05-119 |
| Keywords: | lex |
KSG <kgatlin@cs.ucsd.edu> 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.
Helmut Richter
Return to the
comp.compilers page.
Search the
comp.compilers archives again.