0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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