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

## rpboland@gmail.com8 Sep 2006 16:56:08 -0400

From comp.compilers

Related articles
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 torbenm@app-3.diku.dk (2006-09-08)
Re: Algorithms for finding if two DFA's are equivalent sasha.mal@excite.com (sasha mal) (2006-09-08)
Re: Algorithms for finding if two DFA's are equivalent rpboland@gmail.com (2006-09-08)
| List of all articles for this month |

 From: rpboland@gmail.com Newsgroups: comp.compilers,comp.theory Date: 8 Sep 2006 16:56:08 -0400 Organization: http://groups.google.com References: 06-09-014 Keywords: lex, DFA Posted-Date: 08 Sep 2006 16:56:08 EDT

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

Post a followup to this message