[Haskell-cafe] Regular Expression Simplification

[Doug McIlroy]

Apropos of regular expression simplification,

> My first thought was: Maybe it would be possible to convert the regular
expression to something like an NFA,

>  I'm slightly worried that the overhead of converting to an NFA
is far too great for complicated regular expressions 

"Far too great" is only quadratic in the number of nonterminal
symbols (with repetitions counted) in the regular expression.
And the result is a particularly nice NFA, with one state for
each of those symbols, and no epsilon moves. So I think there's
merit in the proposal. See my Functional Pearl, JFP 14 (2004) 503-518,
http://www.cs.dartmouth.edu/~doug/pubs.html

Doug McIlroy
ok at cs.otago.ac.nz