Which is the best or easiest method for determining equivalence between two automata?
I.e., if given two finite automata A and B, how can I determine whether both recognize the same language?
They are both deterministic or both nondeterministic.
A different, simpler approach is to complement and intersect the automata. An automaton A
is equivalent to B
iff L(A)
is contained in L(B)
and vice versa which is iff the intersection between the complement of L(B)
and L(A)
is empty and vice versa.
Here is the algorithm for checking if L(A)
is contained in L(B)
:
B
using the subset construction. Then, make every accepting state rejecting and every rejecting state accepting. You get an automaton that recognizes the complement of L(B)
.L(B)
and L(A)
. I.e., construct an automaton for the intersection of the automaton from step 1 and A
. To intersect two automata U
and V
you construct an automaton with the states U x V
. The automaton moves from state (u,v)
to (u',v')
with letter a
iff there are transitions u --a--> u'
in U
and v --a--> v'
in V
. The accepting states are states (u,v)
where u
is accepting in U
and v
is accepting in V
.If L(A)
is contained in L(B)
we need to run the same algorithm to check if L(B)
is contained in L(A)
.