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

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