Regular expression that generates dead or redundant DFAs

Question

I want to implement a DFA minimizer in my lexer, but I cannot create a DFA that does not look like the minimum DFA for an expression.

I am creating a DFA from an NFA that is built using the thomson construct from a postfix regex. This is pretty accurate what is described in the book of dragons. To make a lexer, multiple NFAs are combined using epsilon transitions from the start state. This federated NFA uses the DFA algorithm.

So, is there any “known” regular expression that will generate DFA that will make a good test layer to eliminate dead state and minimize state?

I could, of course, just hack the weird DFA and apply the algorithms on it, but wouldn't that be a really valid test case? If it is so that the method I create DFA is not subject to dead states, then this information will be equally significant, because then I can skip the implementation of the state exception function altogether.

Edit: If you need implementation details in order to answer exactly, the code is available on github , specifically NFA.cs and DFA.cs. In addition, I wrote a series of blog posts about a construction algorithm that I use if that helps.

Answer 1

Ok, so I found this in a complete workaround. I made a tool for visualizing regular expressions, since I got a good conclusion from my analyzer. This accurately illustrates such an expression that using standard thompson building methods will give you pretty dumb automata: (a+b+c+)+|abc

Shown in the tool: http://regexvisualizer.apphb.com/?Regex=%28a%2Bb%2Bc%2B%29%2B%7Cabc&NfaSize=300&DfaSize=250#

This tool currently performs the straightforward Thompson design without any optimization. If you remove the part of the |abc expression that is completely redundant, the expression should remain unchanged. This is not true.