Espressione regolare che genera un DFA con stati morti o superflui

Question

Sto cercando di implementare un minimizzatore DFA nel mio lexer, ma non riesco a produrre un DFA che non sembra che sia già il DFA minimo per il espressione.

Sto costruendo il DFA da un NFA che viene costruito utilizzando la costruzione di Thomson da un'espressione regolare postfissa. È praticamente esattamente ciò che viene descritto nel libro del drago. Per far sì che il lexer parecchie delle NFA vengano combinate usando le transizioni epsilon dallo stato di partenza. È su questo NFA combinato che viene applicato l'algoritmo DFA.

Quindi, esiste un'espressione regolare "nota" che genererà un DFA che costituirà un bel banco di prova per l'eliminazione dello stato morto e la riduzione dello stato?

Ovviamente potrei semplicemente creare uno strano DFA e applicare gli algoritmi su di esso, ma non sarebbe un vero e proprio banco di prova? Se è così che il metodo che sto costruendo DFA non è soggetto a stati morti, allora quell'informazione sarebbe altrettanto preziosa, da allora posso saltare l'implementazione della funzione di eliminazione dello stato del tutto.

Edit: Nel caso abbiate bisogno dettagli di implementazione al fine di rispondere con precisione, il codice è disponibile sul github, in particolare i NFA.cs e DFA.cs classi. Inoltre ho scritto una serie su blog posts sull'algoritmo di costruzione che sto usando, se questo aiuta.

Answer 1

Ok, l'ho trovato in modo totalmente indiretto. Ho creato uno strumento per visualizzare le espressioni regolari da quando ho ottenuto un buon output di debug dal mio parser. Questo illustra giustamente una tale espressione che l'utilizzo di tecniche di costruzione standard di Thompson vi darà una abbastanza stupido automi: (a+b+c+)+|abc

Indicato nello strumento: http://regexvisualizer.apphb.com/?Regex=%28a%2Bb%2Bc%2B%29%2B%7Cabc&NfaSize=300&DfaSize=250#

Questo strumento attualmente esegue una scala la costruzione Thompson senza alcuna ottimizzazione. Se rimuovi la parte |abc dell'espressione che è del tutto superflua, l'espressione dovrebbe rimanere la stessa. Non è così.