[Haskell-cafe] Regular Expression Simplification

Doug McIlroy doug at cs.dartmouth.edu
Fri Mar 21 15:05:08 UTC 2014

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,

Doug McIlroy
ok at cs.otago.ac.nz

More information about the Haskell-Cafe mailing list