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

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

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