Why equality is decidable for regular language but not for $CFL?$

Question

There are infinitely many different $PDAs$ for the same $CFL$ exist, therefore we can't check equality for $CFL.$ But also there are infinitely many different $DFA$ exists for same regular language. So why equality of regular is decidable but not for $CFL?$

Answer 1

The short (and not very useful) answer is that we can prove that PDA equivalence is undecidable, and we can prove that DFA equivalence is decidable.

It is important to realize that formally, the above is the only mathematically valid "reason". What you are asking is more about the intuition for this result.

The fact that there are infinitely many DFAs and PDAs that represent the same language is not really important, since in checking equivalence, you are given two fixed automata, and you are checking their equivalence.

The fundamental difference between PDAs and DFAs is their configuration space: you can represent the current "configuration" of a DFA by simply saying what state of the DFA the run is currently at, and from there you can continue reading the word. That is, the state gives you all the information you need to continue.

In contrast, in a PDA you need to know the state of the PDA as well as the entire contents of the stack, otherwise you might not know how to continue the run. Since the stack is unbounded, the number of possible configurations of a PDA is infinite.

Usually, the "reason" problems become undecidable is that there is some underlying infinite configuration space. This is not mathematically accurate, but it's a good intuition.

Thus, when you're checking the equivalence of two automata, you essentially ask "is there a word that reaches a different configuration in the two automata?" (more precisely, can you reach an accepting configuration in one and not in the other). Now, clearly if there is such a word, then there is also such a word such that the runs of the two automata on it don't repeat their configuration. This is because if a configuration is repeated, you can truncate the word and find a shorter one.

When you apply this reasoning to DFAs $A,B$, you get that they are not equivalent iff there is such a word of length at most $|A|\cdot |B|$. This is due to their finite configuration space. This is actually sufficient to prove that their equivalence is decidable.

When you apply this reasoning to PDAs, you don't really get anything, since the configuration space is infinite. Note that this is not sufficient to prove that equivalence is undecidable, but it does suggest that maybe we should look for a proof of undecidability.