27 May 1999 00:43:01 -0400

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.