Decision Algorithms for Equality of Two Languages

Decision questions

We can establish procedures that enable us to make certain decisions about regular languages. For example, we might ask the question, “Do two automata recognize the same regular language?” Two languages are equal if they are the same set of strings.

Two sets are equal if and only if they have the same elements. When the sets are infinite, the best way to establish their equality is to show that any element in one set is also in the other, and vice versa; that is, $L_1=L_2$ if and only if $L_1\subseteq L_2$ and $L_2\subseteq L_1$. Another way to express this idea is that neither set has an element that the other doesn’t. The latter statement is equivalent to the mathematical expression $L_1\ominus L_2=\phi$. Since we know how to compute the symmetric difference of two automata, this is our algorithm for testing language equality.

Testing for equality of two languages

We know that the machines in the following two figures accept the same language since the second is the minimization of the first. To illustrate the procedure testing for equality of languages, let’s verify whether the symmetric difference of those two machines is empty. Let’s call these machines $Q$ and $R$, and both are shown in the following figures.