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

sasha mal <sasha.mal@excite.com>
8 Sep 2006 12:25:35 -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: sasha mal <sasha.mal@excite.com>
Newsgroups: comp.compilers,comp.theory
Followup-To: comp.theory
Date: 8 Sep 2006 12:25:35 -0400
Organization: University of Saarland, Computing Center, Germany.
References: 06-09-014
Keywords: lex, DFA
Posted-Date: 08 Sep 2006 12:25:35 EDT

Roger.Sindreu@gmail.com wrote:
> 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?


Cheers
Sasha.


Post a followup to this message

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