8 Sep 2006 12:25:35 -0400

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

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.