Generating strings from regular expressions

KSG <kgatlin@cs.ucsd.edu>
24 May 1999 01:40:10 -0400

          From comp.compilers
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)
| List of all articles for this month |
From: KSG <kgatlin@cs.ucsd.edu>
Newsgroups: comp.compilers,comp.theory
Date: 24 May 1999 01:40:10 -0400
Organization: Lab Head
Distribution: inet
Keywords: lex, question, comment

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


I've thought about building the NFA and traversing that, but I'm not
sure if building the NFA is really necessary. Is there a simpler way?


Thanks,


KSG
[Simpler? Sure. Enumerate all the strings of length k, run them through
the RE matcher of your choice, and list the one that match. But I will
admit that for large k it could be kind of slow. -John]

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.