I've seen the proof that $EQ_{CFG}$ is not recognizable but its complement is, my problem is that in the proof that it's complement is recognizable, it says that we test every string in $\sum^*$ and checks if it's generated by one of the $CFG$s but not the other. My question is that why don't we use this method to solve $EQ_{CFG}$ problem, where we iterate on all possible strings in $\sum^*$ and confirm that it either gets generated or not by both $CFGs$


The difference here comes from the requirement to halt.

An algorithm that returns "true", must always do so in finite time, hence, it will never be able to go through all strings in $\Sigma^*$ and confirm that it is either generated not by both CFGs.

However, for the complement problem, the requirement changes drastically: It is enough to show one string $w$ such that $w\in L(G_1)$ and $w\notin L(G_2)$ (or vice versa) to know that $L(G_1)\neq L(G_2)$. This allows us to find this string $w$ and halt when we see it, without the need to continue and check more strings.

I hope this gave you some intuition :) (P.S, this is not a formal proof)


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.