|Algorithms for finding if two DFA's are equivalent Roger.Sindreu@gmail.com (2006-09-08)|
|Re: Algorithms for finding if two DFA's are equivalent Szabolcs.Ivan@gmail.com (Szabolcs Ivan) (2006-09-08)|
|Re: Algorithms for finding if two DFA's are equivalent email@example.com (2006-09-08)|
|Re: Algorithms for finding if two DFA's are equivalent firstname.lastname@example.org (sasha mal) (2006-09-08)|
|Re: Algorithms for finding if two DFA's are equivalent email@example.com (2006-09-08)|
|Date:||8 Sep 2006 16:56:08 -0400|
|Posted-Date:||08 Sep 2006 16:56:08 EDT|
> 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.
> 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
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.
Return to the
Search the comp.compilers archives again.