8 Sep 2006 12:24:19 -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: | "Szabolcs Ivan" <Szabolcs.Ivan@gmail.com> |

Newsgroups: | comp.compilers,comp.theory |

Date: | 8 Sep 2006 12:24:19 -0400 |

Organization: | http://groups.google.com |

References: | 06-09-014 |

Keywords: | lex, DFA |

Posted-Date: | 08 Sep 2006 12:24:19 EDT |

If you do not want to minimize the DFA's, then you can

- construct the direct product of the two DFA's (that has states

of the form (p,q), where p\in Q1, q\in Q2 and delta( (p,q),a ) =

(delta(p,a),delta(q,a)); starting state is (q0,q0') )

- check whether for all accessible states (p,q) does it hold that

p\in F_1 iff q\in F_2.

I do not care about cost but have a remark: This method is clearly

polynomial (constructing the product is quadratic, checking all

accessible states is linear in the size of the product automaton, that

is again linear). Moreover, it can be used to decide whether one of

the languages is a subset of the other since L1\subseteq L2 if and

only if for all accessible state (p,q) in the product automaton with

p\in F_1 it holds that q\in F_2. Of course you does not need to

explicitly construct the product automaton, you can traverse its

states generated "on the fly" by any graph traversing algorithm. At

most |\Sigma|*|Q1|*| Q2| steps if checking finals and accessing delta

has a constant time (i.e. finality stored in a boolean array and delta

in a two-dimensional array).

Regards,

Szabolcs Ivan

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.