3 ms·

Thanks. I’ve already added the anchors in fact, when I guessed this might be the problem you were having. I'm also wondering whether it would be possible to g

Thanks. I’ve already added the anchors in fact, when I guessed this might be the problem you were having. I'm also wondering whether it would be possible to generate shorter regular expressions by using a different algorithm for converting the DFA into a regex. I'm using state elimination, which was straightforward to implement, but perhaps the results would be shorter using Brzozowski's algorithm? I'll have a play with that, when I get a spare hour. I'm a little disappointed more people didn't find this interesting, because I would have enjoyed discussing it, but it was a fun hack in any case!

Groxx 16y ago
Submission time seems to play a pretty big role. Looks like this went up around 7pm (here. US Central) - for future reference, try ~4pm for your target, when people get off work ;) I'm almost certain I saw an article here very-roughly a couple months ago that had an example of how to "shrink" regexes to their functional equivalent. Can't find it now, though :\
- robinhouston 16y ago
  Interesting. If you can dig that out, I'd love to see it. The problem of reducing a regular expression to a minimal equivalent is PSPACE-complete, so there's not much hope for a practical exact algorithm, but I don't know what the state of the art is on approximation algorithms for minimisation.