I have been searching for proofs that show that $EQ_{CFG}$ is co-Turing-recognizable. When searching for proofs I can only find proofs on the following form:

Construct a TM $M$ which recognizes the complement of $EQ_{CFG}$, M = "On input ⟨G,H⟩":

  1. For each string $x \in \Sigma^*$ in lexicographic order:
  2. Test whether x ∈ L(G) and whether x ∈ L(H), using the algorithm for $A_{CFG}$ .
  3. If one of the tests accepts and the other rejects, accept; otherwise, continue.”

(From: http://cobweb.cs.uga.edu/~potter/theory/6_reducibility.pdf)

Isn't this proof incorrect?

Say that my language is $\Sigma=\{a,b\}$ and that I have $L(G_1) = \{b\}$ and $L(G_2) = {bb}$. $M$ should accept $\langle G_1, G_2\rangle$ since $L(G_1) \neq L(G_2)$. But if we run $M$ with $\langle G_1, G_2\rangle$ the TM will first generate $x=a$, which isn't in either languages so the machine will go back to step 1 and then generate $x=aa$, then $x=aaa$ and so on forever. The machine will never get to $x=b$. Hence, the machine will loop on input that it should accept. Therefore $M$ isn't a Turing recognizer.

Would the proof be correct if step 1 instead would state "For each string $x \in \Sigma^*$, ordered by increasing size and then lexicographic order:"? This should generate strings in the following order: $x=a$, $x=b$, $x=aa$, $x=ab$, $x=ba$, $x=bb$, $x=aaa$, and so on. So in the case above $M$ would reject when $x=b$.


1 Answer 1


In this context, lexicographic order means:

  • First order by length.
  • Within each length, order lexicographically.

You're saying that the proof is incorrect, but in fact it is only inaccurate in that the order is not quite the lexicographic order. I would say that the proof has a small mistake, but is otherwise correct.

One often encounters such small issues in intricate mathematical arguments. Instead of immediately declaring failure when you run upon such a difficulty, you should try to see if the argument can be fixed by making small adjustments. You're not in a trial, acting as a prosecutor. Rather, you should believe the author that she had some valid proof in mind, but perhaps was a bit sloppy when trying to express her thoughts on paper. It's a cooperative game, in which you are trying to make the proof work rather than try to break it.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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