Algorithms for Compiler Design: EQUIVALENCE OF TWO AUTOMATAS

Automatas M₁ and M₂ are said to be equivalent if they accept the same language; that is, L(M₁) = L(M₂). It is possible to test whether the automatas M₁ and M₂ accept the same language—and hence, whether they are equivalent or not. One method of doing this is to minimize both M₁ and M₂, and if the minimal state automatas obtained from M₁ and M₂ are identical, then M₁ is equivalent to M₂.

Another method to test whether or not M₁ is equivalent to M₂ is to find out if:

For this, complement M₂, and construct an automata that accepts both the intersection of language accepted by M₁ and the complement of M₂. If this automata accepts an empty set, then it means that there is no string acceptable to M₁ that is not acceptable to M₂. Similarly, construct an automata that accepts the intersection of language accepted by M₂ and the complement of M₁. If this automata accepts an empty set, then it means that there is no string acceptable to M₂ that is not acceptable to M₁. Hence, the language accepted by M₁ is same as the language accepted by M₂.