undecidability of CFG equivalence
Here is the first sting in the tail. You can decide whether a single grammar's language is empty, or finite, or contains a given string. But ask a seemingly innocent comparison — do these TWO context-free grammars generate exactly the SAME language? — and there is NO algorithm that always answers correctly. The equivalence problem for context-free grammars is UNDECIDABLE. This is a hard limit, not a matter of waiting for a faster computer or a smarter trick.
What 'undecidable' means here is strict: for every proposed procedure that claims to compare any two grammars, there exist grammars on which it either gives the wrong answer or runs forever without answering. No general decider can exist. The fact is proved by a reduction (worked out in the undecidability part of the theory, not here) from a known-undecidable problem such as the Post correspondence problem: one builds, from any PCP instance, two grammars that are equivalent if and only if the PCP instance has no solution. Since deciding PCP is impossible, deciding grammar equivalence must be impossible too.
The contrast is the whole point. For regular languages, equivalence IS decidable — minimize both DFAs and compare, or take the symmetric difference and test emptiness. The extra power that lets context-free grammars count and nest is exactly the power that makes comparing them undecidable. Even this modest, everyday model — the grammars behind programming languages — already runs headlong into undecidability. (Note: equivalence of DETERMINISTIC context-free languages is decidable, a deep and famous result, but the general context-free case is not.)
Two grammars might generate the same language by entirely different rules — one writing S -> a S b | ε, another writing the same strings through extra intermediate variables. You cannot in general tell whether their languages coincide. By contrast, for two DFAs you simply minimize both and check if the minimal machines match.
Decidable for DFAs, undecidable for CFGs: the same question, opposite verdicts.
Equivalence is undecidable for GENERAL context-free grammars; the special case of DETERMINISTIC CFLs is decidable (a celebrated theorem). Do not generalize the deterministic result to all CFGs.