Re: Algorithms for finding if two DFA's are equivalent

Roger.Sindreu@gmail.com wrote:
> I would like to know all the methods you know for finding if two DFA's
> are equivalent.
>
> I know the trivial algorithm which is finding the mininimum DFA for
> each DFA, and just check if they are equal. Do you know any other
> algorithm? Do not care much about its cost, this is not a goal for me.
>
> If possible, please give references.
>
> Cheers,
> Roger Sindreu.


Let A and B be the DFAs.


1) Treat A and B as if they are NFAs.
2) Construct the DFA (say C) of the NFA A | B using subset
construction.
3) Verify that every state of C was built using at least one state
from A and
            at least one state from B during subset construction.
              if this does not hold then A and B are not equivalent.


Note that this algorithm also works if A and B are NFAs and can also
be used to determine if A is a subset of B and conversely.


I have implemented this algorithm and can attest that it works well.
Minimization is probably the fastest algorithm though.


Ralph Boland

Return to the comp.compilers page.
Search the comp.compilers archives again.