Given a context-free grammar and a regular grammar, check whether they are equivalent. It's a fact that it's undecidable, but how could I prove it?

I want to clarify that my question is not about determining whether a CFG describes a regular language. In my problem I am given a CFG and a regular language and I need to tell whether they are equal or not. These are different problems as far as I understand, mine is easier than that one.


marked as duplicate by Apass.Jack, Evil, xskxzr, Yuval Filmus, Discrete lizard May 14 at 10:40

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.


There is no algorithm which can determine for any context-free grammar $G_1$ and regular grammar $G_2$ whether $L(G_1) = L(G_2)$.

However, it may well be possible to determine for particular $G_1$ and $G_2$, using heuristic proof techniques (aka human intuition).

Good luck with the assignment.


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