|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)|
|From:||sasha mal <firstname.lastname@example.org>|
|Date:||8 Sep 2006 12:25:35 -0400|
|Organization:||University of Saarland, Computing Center, Germany.|
|Posted-Date:||08 Sep 2006 12:25:35 EDT|
> I would like to know all the methods you know for finding if two DFA's
> are equivalent.
> If possible, please give references.
Well, check that the languages of both A x B^c and A^c x B are empty.
X^c is any automaton which accepts complement of the language of X.
since your automata are deterministic (DFA), the complement is trivial
and constructing the product takes quadratic time. Emptieness check
takes linear time in the size of the product.
What is the complexity of the problem for NFAs?
Return to the
Search the comp.compilers archives again.