How can I simplify the regex generated from DFA

Question

I am trying to implement the Brzozowski algebraic method using Java to generate a regular expression of the language accepted by the DFA. Expression is correct, but not simplified.

For example: E|(E)e(e)|(A|(E)e(A))(A|e|(B)e(A))*(B|(B)e(e))|(B|(E)e(B)|(A|(E)e(A))(A|e|(B)e(A))*(E|(B)e(B)))(B|e|(E)e(B)|(A|(E)e(A))(A|e|(B)e(A))*(E|(B)e(B)))*(E|(E)e(e)|(A|(E)e(A))(A|e|(B)e(A))*(B|(B)e(e))) (e = epsilon, E = empty set)

instead: (A|B)*AB

The "transitive closure method" returns almost the same result.

One solution is to minimize the automaton, but I find it too heavy to create a simplified regular expression.

also, using Java regex methods to simplify regex is not at all pretty :).

So, it would be nice to try to help me find a solution.

Answer 1

Yes it is possible. Take a look at this article by Peter Norwig . Oh! The second part . The solution is in python, but you can easily adapt it.