8 Sep 2006 16:56:08 -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: | 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 |

Posted-Date: | 08 Sep 2006 16:56:08 EDT |

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.