Let $A$ and $B$ be two deterministic finite automata. How do we prove that $L_E = \{ \langle A, B \rangle : L(A) = L(B) \}$ is neither regular nor context-free?

Intuitively, I feel that $L_E$ should not be context-free because we must try each string $\in \Sigma^*$ (where $\Sigma$ is the alphabet) and check if the string $\in L(A)$ or $\in L(B)$. However, this reasoning sounds informal to me. How do I formalize this proof?

  • 1
    $\begingroup$ Your heuristic is unfortunately on the wrong track, because it suggests that the problem is undecidable. Given two regular languages you can test whether they are equal by constructing an automaton that accepts their symmetric difference and checking for emptiness. $\endgroup$
    – sdcvvc
    Dec 16 '12 at 0:07

One possible way, is to use the pumping lemma, but one needs to be careful about the details. For simplicity let's discuss only the pumping lemma for regular languages (but I believe a similar method can be used when considering the CFL-pumping lemma).

Let's assume that $\langle A \rangle$ is a well-defined way to encode DFAs, that begins with describing the number of states, then list the transition for each state, etc. Also assume that any string that is not "well formatted" under this encoding just describes a DFA that rejects all words.

Let $n$ be the pumping length.

Let $A=B$ be a $2^n$-state DFA that accepts all words. The encoding of $A$ begins with stating it has $2^n$ states, that is the first part is of length $\log(2^n)=n$ bits at least.

Now let's use the pumping lemma on $w=\langle A,B\rangle$ (which is longer than $n$, so the pumping lemma applies). We can split $w$ into $xyz$ such that $|xy|\le n$, that is, the part we pump "lies" in the part that describes the amount of states in $A$. Now, we pump the word down. That is, consider the words $w'=xz$ which should be also in $L_E$ by the pumping Lemma.

However, we can interpret $w'$ as being $w'=\langle A',B\rangle$ where $A'$ is a malformed encoding (it begins with stating the DFA has less then $2^n$ states, but then it describes transitions of $2^n$ states, which is inconsistent with the claimed number of states).

Therefore, by our assumption $L(A')=\emptyset$ while $L(B)=\Sigma^*$. Thus, $\langle A',B\rangle \notin L_E$ and we reached a contradiction.


Nonregularity - trivial way:

Assuming you encode the pairs as $a \sharp b$ where $a,b$ encode automatas, there are infinitely many Myhill-Nerode classes corresponding to prefixes $a \sharp$. In other words, after reading the $\sharp$ symbol there is an unbounded number of possibilities to remember.

Nonregularity - by nuke:

Assume that the first automaton does not accept anything. By taking a quotient, we can assume the input consists only of the second automaton. We are therefore given a graph and have to check whether an accepting state is reachable. This is effectively the graph reachability problem on a bounded degree graph, which is $\mathsf{NL}$-complete and by the space hierarchy theorem not in $\mathsf{DSPACE}(O(1))$, which is known to be the set of regular languages.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.