21 Mar
2014
21 Mar
'14
11:05 a.m.
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@cs.otago.ac.nz