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

rpboland@gmail.com
8 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

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

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