DFA Minimization Brzozowski algorithm

Question

I am trying to implement Brzozowski's algorithm for minimizing my DFA Following is the algorithm for the same.

DFA = d(r(d(r(NFA)))) 

where r() is reversal of NFA and D() converts NFA to DFA.

But I do not understand what is the meaning of r() searching on google also does not gives much information.

Can anybody please explain what is r() of NFA.

Any other simple algorithm or C++ implementation available please let me know the link.

Answer 1

In the code for reverse.c (found here, but now defunct) you'll find a comment /* Create reversed edges */. So I'd say that r() is reversing the direction of all edges (plus making sure that the reversed automaton has a well defined start state).

Answer 2

This is the implementation from OpenFst.

In this paper is a diagram (page 15) that show results of applying the reverse operation.

An easier way to help understand FSM operations is to use a library like OpenFst to create and manipulable the machines and then visualize the results using Graphviz.