158 g Theory of Computer Science
vI' over 2: satisfying the following: One automaton reaches a final state on
application of w, whereas the other automaton reaches a nonfinal state.
\Ve give below a method. called the comparison method. to test the
equivalence of two finite automata over 2:.
Comparison Method
Let lVJ and 1);1' be two finite automata over 2:. \Ve construct a comparison table
consisting of n + 1 columns. where n is the number of input symbols. The first
column consists of pairs of vertices of the form (q, q'), where q E M and q'
EM'. If (q, g') appears in some row of the first column, then the
corresponding entry in the a-column (a E 2:) is (q", q;'). where qa and q;' are
reachable from q and qt. respectively on application of a (i.e. by a-paths).
The comparison table is constructed by starting with the pair of initial
vertices qin. q(n of M and M'in the first column. The first elements in the
subsequent columns are (qa. q;,), where qa and q;' are reachable by a-paths
from qin and qili' We repeat the construction by considering the pairs in the
second and subsequent columns which are not in the first column.
The row-wise construction is repeated. There are t\VO cases:
Case 1 If we reach a pair (q. q') such that q is a final state of M, and q' is
a non final state of M' or vice versa, we terminate the construction and
conclude that l'Y1 and /vI' are not equivalent.
Case 2 Here the construction is tenninated when no new element appears in
the second and subsequent columns which are not in the first column (i.e.
when all the elements in the second and subsequent columns appear in the first
column). In this case we conclude that M and M' are equivalent.
EXAMPLE 5.1 5
ConSIder the fo]]owing two DFAs AI and M' over {O, I} given in Fig. 5.23.
Determine whether M and i'v1' are equivalent.
c
(a)
(b)
Fig. 5.23 (a) Automaton M and (b) automaton M'.
vI' over 2: satisfying the following: One automaton reaches a final state on
application of w, whereas the other automaton reaches a nonfinal state.
\Ve give below a method. called the comparison method. to test the
equivalence of two finite automata over 2:.
Comparison Method
Let lVJ and 1);1' be two finite automata over 2:. \Ve construct a comparison table
consisting of n + 1 columns. where n is the number of input symbols. The first
column consists of pairs of vertices of the form (q, q'), where q E M and q'
EM'. If (q, g') appears in some row of the first column, then the
corresponding entry in the a-column (a E 2:) is (q", q;'). where qa and q;' are
reachable from q and qt. respectively on application of a (i.e. by a-paths).
The comparison table is constructed by starting with the pair of initial
vertices qin. q(n of M and M'in the first column. The first elements in the
subsequent columns are (qa. q;,), where qa and q;' are reachable by a-paths
from qin and qili' We repeat the construction by considering the pairs in the
second and subsequent columns which are not in the first column.
The row-wise construction is repeated. There are t\VO cases:
Case 1 If we reach a pair (q. q') such that q is a final state of M, and q' is
a non final state of M' or vice versa, we terminate the construction and
conclude that l'Y1 and /vI' are not equivalent.
Case 2 Here the construction is tenninated when no new element appears in
the second and subsequent columns which are not in the first column (i.e.
when all the elements in the second and subsequent columns appear in the first
column). In this case we conclude that M and M' are equivalent.
EXAMPLE 5.1 5
ConSIder the fo]]owing two DFAs AI and M' over {O, I} given in Fig. 5.23.
Determine whether M and i'v1' are equivalent.
c
(a)
(b)
Fig. 5.23 (a) Automaton M and (b) automaton M'.