I know that the equivalence of two context-free grammars is undecidable, but what about the equivalence of a regular grammar and a context-free grammar?


1 Answer 1


It is undecidable whether for a given CFG $G$, $L(G)=\Delta^*$, the set of all strings (over the terminal alphabet of $G$). That answers your question, by chosing the most simple regular grammar.

  • 2
    $\begingroup$ I thought the most simple regular language was the empty one. ;) $\endgroup$
    – babou
    Mar 4, 2015 at 1:25
  • $\begingroup$ Ah, that's excellent. Thanks, Hendrik! $\endgroup$ Mar 4, 2015 at 2:35
  • 1
    $\begingroup$ @babou Indeed. You made me smile. Nevertheless the concept "empty language" might be very confusing to some. In a recent exam some students noted that $\{a,b,c,d\}$ had $17$ subsets: $2^4$ usual ones, plus the empty set. $\endgroup$ Mar 4, 2015 at 17:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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