Enumerating the Strings of a Regular Expression

Abstract

We present a Haskell solution to the problem of enumerating the strings of a regular expression with respect to a regular preorder, a term we soon define. A version of this problem was considered in a note by Jayadev Misra. We have generalized the problem. The use of Haskell was suggested by Edsger W. Dijkstra and our solution makes critical use of Haskell's lazy evaluation.

Gzipped Postscript (55K)
Haskell Code (4K)

Last updated October 2001 manolios@cc.gatech.edu

Back to Pete's home page College of Computing