3 ms·

Here's the paper that shows how to do the direct construction of the minimal DFA in linear time: http://acl.ldc.upenn.edu/J/J00/J00-1002.pdf http://acl.ldc.upen

• danieldk 13y ago
  And my implementation in Java :): https://github.com/danieldk/dictomaton https://github.com/danieldk/dictomaton
• noprompt 13y ago
  This is interesting. Thank you for sharing the link to this paper. At the moment I believe I have something that looks similar Figure 1, however, the algorithm is nothing to write home about. I wrote the initial version one afternoon and didn't do a tremendous amount of research regarding the problem. In fact, most of the commits I've made to the project have been to the README! I definitely would like to work towards something that more closely resembles Figure 2 and emit the most optimal regular expression possible. Naturally that means I would be rewriting most of it. :) Again, thanks for sharing this.