Add feature to minimize the DFA

[SicroAtGit]

Add a new function that creates a new DFA from the existing DFA that has been minimized to the states that are really needed.

For example, the RegEx ab|cb creates this DFA:

The minimized DFA would look like this:

[tajmone]

Guangming Xing Algorithm

For the minimization algorithm, see the paper Minimized Thompson NFA by Guangming Xing, which provides an improved approach to the classic method, resulting in smaller trees, less auxiliary states, and it's faster.

The problem of converting a regular expression to NFA is a fundamental problem that has been well studied. However, the two basic construction algorithms: (1) Thompson, (2) McNaughton-Yamada and Glushkov, both have disadvantages.
In this paper: First, a "smart" parsing algorithm is developed which constructs a parse tree with at most (3l − 1) nodes form a regular expression with l literals; Second, we propose an algorithm that works on the resulting NFA from Thompson's construction, eliminating as many auxiliary states as possible while maintaining Thompson's properties.
It is shown that the resulting NFA is minimized. This means that no auxiliary states can be eliminated without violating the defining properties of Thompson NFA. The time and space requirement for the above algorithms are linear with respect to the length of the regular expression. To the author's knowledge, this is the first linear time algorithm minimizing an NFA in a precise technical sense.

[SicroAtGit]

Yes, it would be good if there was also minimization for the NFA in the RegEx engine. The DFA would also benefit from this.

In the paper, the first algorithm requires a parse tree as input. In the RegEx engine, no parse tree is created. The second algorithm needs an NFA as input, so it could work in my RegEx engine.

Thanks, will have a look after the final version 1.0 is released.