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

torbenm@app-3.diku.dk (=?iso-8859-1?q?Torben_=C6gidius_Mogensen?=)
8 Sep 2006 12:24:46 -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: torbenm@app-3.diku.dk (=?iso-8859-1?q?Torben_=C6gidius_Mogensen?=)
Newsgroups: comp.compilers,comp.theory
Followup-To: comp.theory
Date: 8 Sep 2006 12:24:46 -0400
Organization: Department of Computer Science, University of Copenhagen
References: 06-09-014
Keywords: lex, DFA
Posted-Date: 08 Sep 2006 12:24:46 EDT

Roger.Sindreu@gmail.com writes:


> 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.


You can test for bisimulation.


Or you can construct a DFA for the complement language of one of the
DFAs and then the intersection between this and the other and finally
test for emptyness.


From the pumping lemma, we can see that two DFAs are equivalent of
they agree on all strings under a certain length (that depends on the
number of states in the DFAs). So compute this length and compare the
DFAs on all strings under this length. This is bound to be the least
efficient way of testing equivalence.


                    Torben


Post a followup to this message

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