4

I try to implement the Brzozowski algebraic method using Java, to generate the regular expression of the langage accepted by a given DFA, The expression generated 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 = the empty set)

instead of : (A|B)*AB

The "Transitive closure method" returns nearly the same result.

One of the solutions consists of minimizing the automaton, but i think it's too heavy to generate a simplified regular expression.

also, using Java regular expressions methods to simplify a regular expression is not pretty at all :) .

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

CAustin
  • 4,525
  • 13
  • 25
Elh.yas
  • 41
  • 3
  • I don't know the answer to your question. This answer in the [Stack Overflow Regular Expressions FAQ](http://stackoverflow.com/a/22944075/2736496) may be of interest, though: [DFA versus NFA](http://stackoverflow.com/questions/3978438/dfa-vs-nfa-engines-what-is-the-difference-in-their-capabilities-and-limitations), as listed in the "General" section. – aliteralmind Apr 17 '14 at 01:59
  • The dk.brics.automaton library contains a few different minimization algorithms that you might study. I don't think that library can convert an automaton back into a regular expression, but you seem to already know how to do that. – Kevin Krumwiede Apr 17 '14 at 02:12
  • This looks like an Automata homework question. I would highly advise showing more insight into what you're trying to accomplish as well as any attempts you've tried. Showing you've taken a crack at the problem will provide motivation for giving you assistance. – signus May 06 '14 at 22:44

1 Answers1

0

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

neves
  • 33,186
  • 27
  • 159
  • 192